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.
Office hours: Mondays
2003 Fall Semester, Mondays and Wednesdays, ,
Examples: Metric TSP, Max Cut.
Scribe notes for lecture 1: lecture1.ps
Combinatorial bounds: Chromatic Index.
Randomized rounding: Max SAT.
Extensions of metrics: Multiway cut.
Assignment 2 is
out: Due date:
Semidefinite relaxations: Max Cut.
The primal-dual schema: Steiner tree.
Lagrangian relaxations: k-MST.
Facility location – a test case: IP formulation, LP relaxation, LP rounding.
Scribe notes for lectures 16 and 17: lectures16and17.ps
(= take home exam) is out. Due date:
Hardness of approximation: Probabilistically checkable proofs, inapproximability.
Scribe notes for lecture 23: lecture23.ps
· 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 September 8, 2003