Approximability of Optimization Problems (Fall 1999)

A complexity-theoretic view of combinatorial optimization.

Prereq: 6.042, 6.045, 6.046.
Instructor: Madhu Sudan
Time: MW 2:30-4:00pm
Location: 24-307
3-0-9 H-Level Grad Credit
Homepage: http://theory.lcs.mit.edu/~madhu/FT99/course.html

Course announcement

References

I’ll be adding material here as we go along. For now here are some sources for approximation algorithms; and hardness of approximations.

• Preliminary version of a book on Approximation Algorithms by Rajeev Motwani, 1992.
• Approximation Algorithms for NP-hard Problems. Dorit Hochbaum (Ed.), PWS Publishers, 1996.
• Preliminary version of a book on Approximation Algorithms by Vijay Vazirani, 1997 (updated 1999).
• Lecture notes on Approximation Algorithms (Fall 1998) by David P. Williamson.
• Chapter on Hardness of Approximations by Sanjeev Arora and Carsten Lund. This material is part of the book Approximation Algorithms for NP-hard problems edited by D. Hochbaum and listed above. Copyrights for the material are held by PWS Publishing with all rights reserved.

Topics covered so far

• Lecture 1 (9/8): Introduction to NP, NP Optimization, Approximation. Brief History.
• Lecture 2 (9/13): Approximation algorithms for TSP, Vertex Cover, and Knapsack. Fully Polynomial Time Approximation Schemes (FPTAS) and Strong NP-Completeness.
• Lecture 3 (9/15): LP and IP (in constant # of variables). Minimizing Makespan. PTAS for Minimizing Makespan.
• Lecture 4 (9/20): 4/3-approximation of MAX SAT. Vertex Cover revisited; Half-integrality of the LP formulation; Consequences.
• Lecture 5 (9/22): Guest Lecture by Michel Goemans: Approximations via the Primal-Dual method.
• Lecture 6 (9/27): Set Cover. Minimum Multicut (and metric relaxations).
• Lecture 7 (9/29): Minimum Multicut (contd.). Opening negative results. Approximation preserving reductions. Gap Problems.
• Lecture 8 (10/4): Gap Problems. The necessity of probabilistic proof systems. Brief history of probabilistic proof systems: IP, MIP, OIP, PCP.
• Lecture 9 (10/6): PCP and the Hardness of Approximations. Max Clique, Max 3SAT.
• Lecture 10 (10/13): Tools for PCP: Error correcting codes. Reed-Solomon codes (univariate polynomials); Reed-Muller codes (multivariate polynomials); Hadamard codes (linear polynomials). Codes via concatenation.
• Lecture 11 (10/20): Tools for PCP: Self-correction algorithms. Self-correctors for Hadamard and multivariate polynomials. Self-correction with a prover.
• Lecture 12 (10/25): Tools for PCP: Self-testing algorithms. A Self-tester for Hadamard codes: The Blum-Luby-Rubinfeld test for linearity.
• Lecture 13 (10/27): Linearity testing (contd.): Fourier transforms and the linearity test.
• Lecture 14 (11/1): Low Degree Testing: Testing on axis-parallel lines, Testing via random lines; Properties of random lines.
• Lecture 15 (11/3): Low Degree Testing: The lines vs. points test for multivariate polynomials. Reduction to testing bivariate polynomials on axis parallel lines.
• Lecture 16 (11/8): Low Degree Testing: Testing bivariate polynomials.
• Lecture 17 (11/10): PCP via Hadamard codes: An exponential sized PCP for NP. PCP via polynomials; The Constraint satisfaction problem for polynomials.
• Lecture 18 (11/15): Hardness of the constraint satisfaction problem for polynomials.
• Lecture 19 (11/17): A 3-prover 1-round proof system for NP. Composition of proof systems: Outer verifier and Inner verifiers.
• Lecture 20 (11/22): Composition of proof systems. Proof of the PCP theorem.
• Lecture 21 (11/24): Current versions of the PCP theorem. Parallel repetition and improved outer verifiers. Hastad’s inner verifier.
• Lecture 22 (11/29): Back to hardness of approximations: Gadget construction.
• Lecture 23 (12/1): Tailormade PCPs: Zero-knowledge and the chromatic number.
• Lecture 24 (12/6): MIPs and hardness of approximation: Set Cover.
• Lecture 25 (12/8): Concluding thoughts.

For future scribes, here is a sample file and the preamble.tex file that it uses.