COM S 783 / OR&IE 634
Approximation Algorithms

This is a graduate level course on the design and analysis of combinatorial approximation algorithms for NP-hard optimization problems. The initial few lectures will be devoted to a quick review of classical results. The main part of the course will emphasize recent methods and results. The course is tailored for students with a strong inclination towards theory. However, students interested in networks, computer vision, computational biology, and other areas could benefit from this course.

Prerequisites: There are no specific prerequisites. However, students are expected to possess elementary knowledge in graph theory, computational complexity, linear programming, and the probabilistic method. A few good sources for such knowledge are listed below under “references.” We will need just a tiny portion of their content.

Grading policy: The final grade will be based on grading scribe notes, homework assignments, and a take-home exam.

Tentative syllabus:

  • Introduction: optimization, approximation, bounding the optimum.
  • Combinatorial bounds, greedy, local search, rounding, local ratio, dynamic programming, sampling.
  • Randomized rounding, iterative rounding.
  • Region growing, extensions of metrics, bi-Lipschitz embeddings, semidefinite relaxations.
  • The primal-dual schema, Lagrangian relaxations.
  • Hardness of approximation: the PCP theorem, approximation preserving reductions.

Teaching staff:

Office hours: Mondays 2:30 – 3:30 PM

Office: Rhodes 234

  • TA:                  Martin Pal

Meets on: 2003 Fall Semester, Mondays and Wednesdays, 1:00 – 2:15 PM, Rhodes 280.

 

Lectures

  1. Introduction: Optimization, approximation, bounding the optimum.

Examples: Metric TSP, Max Cut.

Scribe notes for lecture 1: lecture1.ps

  1. More examples: Max Cut (cont.), Set Cover.
  2. More examples: Vertex Cover, Knapsack.

Assignment 1 is out. Due date: September 29, 2003. assign1.ps   solutions

Scribe notes for lectures 2 and 3: lecture2.ps – lecture3.ps

  1. Knapsack (cont.)

Combinatorial bounds: Chromatic Index.

  1. Chromatic Index (cont.)

Randomized rounding: Max SAT.

Scribe notes for lectures 4 and 5: lecture4.ps – lecture5.ps

  1. Max SAT (cont.), integral multicommodity flow.
  2. Region growing: Multicut.

Scribe notes for lectures 6 and 7: lecture6.ps – lecture6.pdf – lecture7.ps – lecture7.pdf

  1. Multicut (cont.)

Extensions of metrics: Multiway cut.

  1. Multiway cut (cont.)

Assignment 2 is out: Due date: October 20, 2003. assign2.ps

Scribe notes for lectures 8 and 9: lecture8.ps – lecture8.pdf – lecture9.ps – lecture9.pdf

  1. Bi-Lipschitz embeddings: Sparsest Cut.
  2. Sparsest Cut (cont.), low distortion embeddings into l1, balanced cuts.

Scribe notes for lectures 10 and 11: lecture10.ps – lecture11.ps

  1. Spreading metrics: Linear Arrangement.
  2. Dominating tree metrics: low distortion probabilistic embeddings.

Assignment 3 is out: Due date: November 10, 2003. assign3.ps   solutions

Unchecked drafts of scribe notes for lectures 12 and 13: lecture12.ps – lecture12.pdf – lecture13.ps – lecture13.pdf

  1. (cont.) Metric Labeling.

Semidefinite relaxations: Max Cut.

  1. (cont.) Max Cut.

The primal-dual schema: Steiner tree.

Scribe notes for lectures 14 and 15: lecture14.ps – lecture15.ps

  1. Prize collecting Steiner tree.

Lagrangian relaxations: k-MST.

  1. k-MST (cont.)

Facility location – a test case: IP formulation, LP relaxation, LP rounding.

Scribe notes for lectures 16 and 17: lectures16and17.ps

  1. A primal-dual facility location algorithm.

Last assignment (= take home exam) is out. Due date: December 3, 2003. assign4.ps

Scribe notes for lectures 17 and 18: lecture17.ps – lecture18.ps

  1. Local search facility location.
  2. Greedy facility location.

Hardness of approximation: Probabilistically checkable proofs, inapproximability.

Scribe notes for lectures 19 and 20: lecture19.ps – lecture19.pdf – lecture20.ps – lecture20.pdf

  1. The PCP theorem.
  2. One-round two-prover interactive proof systems, parallel repetition, the long code.

Scribe notes for lectures 21 and 22: lectures21and22.ps – lectures21and22.pdf

  1. The three-bit test and hardness of approximating 3LIN.

Scribe notes for lecture 23: lecture23.ps

  1. Fourier analysis of the three-bit test.

Textbooks

·        V.V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001.

·        D.S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1997.

References

·        N. Alon and J.H. Spencer. The Probabilistic Method, 2nd edition, Wiley, 2000.

·        B. Bollobas, Modern Graph Theory, Springer, 1998.

·        R. Diestel. Graph Theory, Springer, 1997.

·        M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, 2nd corrected edition, Springer-Verlag, 1993.

·        C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

·        A. Schrijver. Theory of Linear and Integer Programming, Wiley, 1986.

·        M. Sipser. Introduction to the Theory of Computation, PWS Publishing Company, 1997.

Lecture notes on linear programming by Michel Goemans

Sample scribe notes can be found here:             lecture1.tex                   scribe notes header file:             approx-header.sty

Last updated on September 8, 2003