Approximation Algorithms

This is a graduate level course
on the design and analysis of combinatorial approximation algorithms for
NP-hard optimization problems. 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**: 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 homework assignments, and a take-home exam.

**Tentative syllabus**: The course is approximately
equally divided into three sections:

- An introduction to approximation algorithms and classical results: optimization, approximation, bounding the optimum, combinatorial bounds, greedy, local search, rounding, local ratio, dynamic programming.
- Advanced methods: sampling, randomized rounding, iterative rounding, region growing, semidefinite relaxations, embeddings, the primal-dual schema, Lagrangian relaxations.
- An introduction to hardness of approximation and the PCP theorem.

**Teaching staff**:

**Instructor**: Prof. Yuval Rabani

**Office hours**: Sundays,

**Office**: Taub 611.

**TA:**Dmitri Pechyony

**Meets on**:
2004-5 Winter Semester, Thursdays,

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

Last updated on