﻿ Approximation Algorithms

Final homework assignment

# 236521 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:

Office hours: Sundays, 10:30 – 11:30.

Office: Taub 611.

Meets on: 2004-5 Winter Semester, Thursdays, 12:30-14:30, Taub 8.

## The following are lectures given at Cornell University last year. I will update the lectures to reflect this year's course at the Technion as we go along.

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

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

·        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 October 28, 2004.