Prof.Swamy will teach a course in Algorithmic Game Theory in the S08 term, Tue, Thu, 1:00-2:20pm in MC 4060.
Assignments 20%-30% Scribing lecture notes 30%-40% Project 30%-40%
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).
Vijay Vazirani, Approximation Algorithms. ( homepage).
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 (G.Tech), CS 8002: Probabilistically Checkable Proofs and Hardness of Approximation, F04
Roughgarden (Stanford), CS359: Hardness of Approximation, W07
Salavatipour (UA), CMPUT 675: Topics on Approximation Algorithms and Approximability, F07
Tentative course outline text
Here are pointers to some relevant papers. Some are references for the lectures.
L.Lovasz, Semidefinite programs and combinatorial optimization, 2000 (postscript, 54 pages)
B.S.Baker, Approximation algorithms for NP-complete problems on planar graphs, J.ACM 1994, 41, 153 - 180
N.Bansal, R.Khandekar, V.Nagarajan,
Additive Guarantees for Degree Bounded Direct Network Design (PDF, IBM report).
STOC 2008 (to appear).
Also posted on this web page.
H.L.Bodlaender, A.M.C.A.Koster, Combinatorial Optimization on Graphs of Bounded Treewidth, The Computer Journal, July 2007 (survey paper)
B.Chor and Madhu Sudan, A Geometric Approach to Betweenness, SIAM J.DM 11(4) 1998:511-523.
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.E.Knuth, The sandwich theorem (postscript or PDF) Expository notes on Lovasz's theta function.
L.C.Lau, J.Naor, M.R.Salavatipour, M.Singh, Survivable network design with degree or order constraints, STOC 2007.
Williamson's notes on PTAS for Euclidean TSP
Wikipedia entry on Treewidth
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 18 Jan. 08 (last update: Jan.10)
Assignment 2, due 1 Feb. 08 (last update: Jan.25)
Assignment 3, due 29 Feb. 08 (last update: Feb.18)
Assignment 4 - Optional, due 11 Apr. 08 (last update: Mar.27)