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**:

**Instructor**: Prof. Yuval Rabani

**Office hours**: Mondays

**Office**:

**TA:**Martin Pal

**Meets on**:
2003 Fall Semester, Mondays and Wednesdays,

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

Examples: Metric TSP, Max Cut.

Scribe notes for lecture 1: lecture1.ps

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

Assignment 1 is
out. Due date:

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

- Knapsack (cont.)

**Combinatorial
bounds**: Chromatic Index.

- Chromatic Index (cont.)

**Randomized
rounding**: Max SAT.

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

- Max SAT (cont.), integral multicommodity flow.
**Region growing**: Multicut.

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

- Multicut (cont.)

**Extensions of
metrics**: Multiway cut.

- Multiway cut (cont.)

Assignment 2 is
out: Due date:

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

**Bi-Lipschitz embeddings**:- Sparsest Cut (cont.), low distortion embeddings into l
_{1}, balanced cuts.

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

**Spreading metrics**: Linear Arrangement.**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

- (cont.) Metric Labeling.

**Semidefinite**** relaxations**: Max Cut.

- (cont.) Max Cut.

**The
primal-dual schema**: Steiner tree.

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

- Prize collecting Steiner tree.

**Lagrangian**** relaxations**: *k*-MST.

*k*-MST (cont.)

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

Scribe notes for lectures 16 and 17: lectures16and17.ps

- A primal-dual facility location algorithm.

Last assignment
(= take home exam) is out. Due date:

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

- Local search facility location.
- 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

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

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

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

Scribe notes for lecture 23: lecture23.ps

- Fourier analysis of the three-bit test.

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

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

· 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