﻿ Approximation Algorithms

# 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.pslecture3.ps

1. Knapsack (cont.)

Combinatorial bounds: Chromatic Index.

1. Chromatic Index (cont.)

Randomized rounding: Max SAT.

Scribe notes for lectures 4 and 5: lecture4.pslecture5.ps

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

Scribe notes for lectures 6 and 7: lecture6.pslecture6.pdflecture7.pslecture7.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.pslecture8.pdflecture9.pslecture9.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.pslecture11.ps

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.pslecture12.pdflecture13.pslecture13.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.pslecture15.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.pslecture18.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.pslecture19.pdflecture20.pslecture20.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.pslectures21and22.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.