CO754 Approximation Algorithms in Combinatorial Optimization - Winter 2010


First meeting: Tuesday, Jan. 5, in MC 2018 B, 10:00am

Course Info

This is an introductory, grad level course.

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.
(Similar courses have been offered in W'05, W'08, W'09 and the plan is to offer this course regularly.)

Time & Place

10:00-11:20am Tue, Thu, MC 2018 B (First meeting: Jan.5 Tuesday)


J.Cheriyan, MC6067, phone: 35591 Office Hours: Tuesdays 12:00-1:00pm


An undergraduate course on the design and analysis of algorithms, including NP-completeness, and an undergraduate course in linear programming.

Grading scheme (Tentative)

Assignments		50%
Project			50%

Lecture Contents (Tentative)

text file

Texts, Monographs, Lecture Notes, Other Courses

Main Text:
Vijay Vazirani, Approximation Algorithms. ( homepage).

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, W08

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

Fujito's survey paper, Approximation Algorithms for Submodular Set Cover with Applications, survey, IEICE Trans Inf Syst (2000)


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.

Assignment 1, due Jan. 19 (Tue), in class PDF
Update for Q4(b) of Ass.1: Each subset has unit cost, thus c_j=1 for all j.

Assignment 2, due Jan. 29 (Fri), 5pm (last update: Jan.26) PDF

Assignment 3, due Feb. 12 (Fri), 5pm (last update: Feb.2) PDF

Assignment 4, due Mar. 26 (Fri), 5pm (last update: Mar.13) PDF

Talks by students and Projects for the course

Schedule of talks on April 6, 7, 8

(html file) (text file)

Due dates for submissions/talks:
note on topic (1 page) Feb.26 (Fri)
report on key results (5 pages) Mar.19 (Fri), 5pm
prelim project report (around 10-15 pages) April.5 (Mon), 3pm
talks April.6,7,8 during 10am-3:30pm
final project report (around 10-15 pages) April.15 (Thu), 5pm


F.Alizadeh, papers on SDPs

N.Bansal, R.Khandekar, V.Nagarajan, Additive Guarantees for Degree Bounded Direct Network Design (PDF, IBM report), STOC 2008.
Also posted on this web page.

M.X.Goemans, papers on SDPs The original "max cut paper" (with D.P.Williamson) is posted here, as well as two survey papers.

D.R.Karger, A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem, SIAM Review 43,3 (2001), pp.499-522 (postscript or PDF)

D.E.Knuth, The sandwich theorem (postscript or PDF) Expository notes on Lovasz's theta function.

L.C.Lau and M.Singh, Iterative rounding and relaxation, survey paper in RIMS Kokyuroku Bessatsu, Kyoto, 2009 (PDF, 22 pages)

L.Lovasz, Semidefinite programs and combinatorial optimization, 2000 (postscript, 54 pages)

L.Trevisan, Inapproximability of Combinatorial Optimization Problems, Jul.2004, revised: Feb.2010

Lecture notes from DIMACS Tutorial on Limits of Approximation Algorithms: PCPs and Unique Games, July 2009

Indiana University, Bloomington, summer school on Analysis and geometry in the theory of computation, 2009 Tutorial notes on Sparsest Cuts and {L_1} embeddings, and UGC, semi-definite programs, and constraint satisfaction. Also see overview by J.Lee

Lecture Notes

Submodular Set Covering (SSC) (last update: Feb.2) PDF
PTAS for Euclidean TSP (last update: Jan.28) PDF (some figures on p.3 got messed)
Gap preserving reductions (last update: Feb.2) PDF (last page is buggy -- spot it)
Bounded-degree MST and MCST via iterative rounding (last update: Mar.25) PDF

last update of page: Mar 2010