First meeting: Wednesday, Jan. 4, in MC 5136B, 2:30pm
Many of the problems that arise in practical applications of discrete
optimization are NP-hard, that is optimal solutions cannot be computed
in polynomial-time modulo the P not equal NP conjecture. Current
research is focusing on the design of polynomial-time approximation
algorithms for such problems.
The course will study some of the successful paradigms for designing
approximation algorithms and for proving approximation guarantees: the
greedy method, formulating and solving LP (linear programming)
relaxations, the (LP based) primal-dual method, randomized rounding,
semidefinite programming relaxations, approximation of metrics, etc.
Some lectures will focus on the hardness of approximating specific problems.
The plan is to cover a good fraction of Vazirani's book in the lectures, and
also to cover some of the more recent results, e.g., from the
recent text of Williamson and Shmoys.
(Similar courses have been offered in W'05, W'08, W'09, W'10, W'11.)
Assignments 50% Project 50%
Main Texts:
Vijay Vazirani,
Approximation Algorithms.
( homepage).
David Williamson and David Shmoys, The Design of Approximation Algorithms. ( homepage, PDF of book available).
Text on Computational Complexity:
Sanjeev Arora and Boaz Barak,
Complexity Theory: A Modern Approach.
( homepage).
PDF files for each chapter and the whole book are on the web;
some of the relevant parts are
Chapter 2, NP and NP completeness,
( PDF),
Chapter 18, PCP and hardness of approximation,
( PDF).
David Williamson, Lecture Notes on Approximation Algorithms, Fall 1998. IBM Research Report RC 21273, February 1999. ( homepage).
Michel Goemans has course notes on randomized algorithms, approximation algorithms, etc. ( homepage).
Cheriyan and Ram Ravi, Lecture Notes on Approximation Algorithms for Network Problems, ( lec notes page).
Hochbaum, D.S. (1996). Approximation algorithms for NP-hard problems. (Boston: PWS publishing co.).
P.Crescenzi, and V.Kann. A compendium of NP optimization problems ( homepage).
David Johnson's NP-Completeness Columns (PDF files for all)
The NP-Completeness Column: The Many Limits on Approximation, David S. Johnson, ACM Transactions on Algorithms (TALG) 2(3):473-489 (July 2006)
Charikar (Princeton), CS 594: Limits on Approximation, S07
Chekuri (UIUC), CS 598: Approximation Algorithms, F06
Gupta & Ravi (CMU), 15-854: Approximation Algorithms, F05
Guruswami & O'Donnell (U.Wash.), CSE 533: The PCP Theorem and Hardness of Approximation, F05
Khot (NYU), G22.3033-007: Probabilistically Checkable Proofs and Hardness of Approximation, S08
Roughgarden (Stanford), CS359: Hardness of Approximation, W07
Salavatipour (UA), CMPUT 675: Topics on Approximation Algorithms and Approximability, F07
Sudan (MIT), Approximability of Optimization Problems, F99
Trevisan (Stanford), CS359G: Graph Partitioning and Expanders, S11
Students are allowed to collaborate on the assignments to the extent of formulating ideas as a group. Each student is expected to write up the solutions by himself or herself. All hints, collaboration, outside help etc. should be explicitly listed in your submission.
Fujito's survey paper, Approximation Algorithms for Submodular Set Cover with Applications, survey, IEICE Trans Inf Syst (2000)
Chernoff Bounds PDF
Garg, Konjevod, Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem, J.Algorithms (2000)
O(log n/ log log n)-approximation algorithm for ATSP PDF
Asadpour, Goemans, Madry, Oveis Gharan, Saberi An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem. SODA 2010: 379-389 Also, see Sato's notes/slides from CO754-W2010
Knapsack problem -- DP and FPTAS PDF
PTAS for Euclidean TSP PDF
Sanjeev Arora, Approximation schemes for NP-hard geometric optimization problems: a survey (postscript, author's page) OR Math. Programming B 97, 43--69, 2003, DOI: 10.1007/s10107-003-0438-y (PDF available via UW)
Simons Foundation, Featured Article Approximately Hard: The Unique Games Conjecture
Trevisan, On Khot's Unique Games Conjecture, Bulletin AMS 49:1, 91-111, 2012
Khot, On The Unique Games Conjecture, 25th Annual IEEE Conference on Computational Complexity (CCC) 2010
Trevisan, Bourgain's embedding of any metric into L1 (CS359G, lec.9)