Tentative Calendar
Week  Topic  Handouts 
Scribe 
Suggested
Reading 
Sep 11 
Overview of course Intro: NPcompleteness & approximation algorithms Elementary probability theory 
Approximation Algorithms 
Vazirani, Ch
1 

Sep 15, 18 
Chernoff bounds Probabilistic method and applications Lovasz Local Lemma 
Probabilistic
Method Chernoff Bounds & LLL 
Dimitrios Kanoulas Eric Miles 
AlonSpencer, Ch 15 
Sep 22, 25 
Proof of LLL and example applications Application of LLL to packet routing 
General
LLL & Applications Packet Routing 
Eric Miles Dimitrios Kanoulas 
LeightonMaggsRao 
Sep 29, Oct 2 
Constructive proof of LLL The counting argument Entropy compression argument 
Harsh Chamarthi 
Moser MoserTardos Spencer Tao Vazirani, Ch 12 

Oct 6, 9 
Randomized rounding: routing and set cover Linear Programming: geometry and duality 
Randomized
Rounding & LP Geometry 

Goemans
notes on LP 
Oct 13, 16 
Deterministic rounding: Facility location Dualfitting analysis: Facility location 
Problem Set 1 Facility Location: Filtering Facility Location: DualFitting 
LinVitter ShmoysTardosAardal MettuPlaxton 

Oct 20, 23 
Primaldual framework: set cover Primaldual framework: Steiner Forest 
PrimalDual and Steiner Forest

GoemansWilliamson Vazirani, Ch 15 

Oct 27, 30 
No class Tuesday Steiner Forest, contd 

Nov 3, 6 
Steiner Forest, contd Iterative rounding: Generalized Network Design 
Steiner Network, part 1 
Jain 

Nov 10, 13 
Generalized Network Design, contd 
Steiner Network, part 2  
Nov 17, 20 
Approximating general metrics by tree metrics 
Wu Jiang  FakcharoenpholRaoTalwar 

Nov 24 
Multiplicativeupdate: Online learning 
Scott Roche 
AroraKaleHazan 

Dec 1, 4 
Multiplicativeupdate: Multicommodity flow No class on Friday 
Scott Roche 
GargKonemann Young 

Dec 8, 11 
Hierarchical decompositions and oblivious routing 
Abutalib Aghayev 
Racke 

Dec 15, 18 
Student presentations 
References
Books
Vijay Vazirani, Approximation Algorithms,
SpringerVerlag,
Berlin, 2001.
Rajeev Motwani and
Prabhakar Raghavan, Randomized
algorithms, Cambridge
University Press, New York, NY, 1995.
Michael Mitzenmacher and
Eli Upfal, Probability and Computing,
Cambridge University Press, 2006
Bernard Korte and Jens
Vygen,
Combinatorial Optimization: Theory
and Algorithms, 3rd edition,
Springer, 2005.
Noga Alon and Joel Spencer,
The Probabilistic Method,
Wiley.
The Probabilistic Method & Lovasz Local Lemma
N. Alon and
J. Spencer, The Probabilistic Method, Chapter 4
F.T. Leighton, B. Maggs, and S. Rao, Packet routing and
jobshop scheduling in O(congestion+dilation)
steps, Combinatorica
1994
Robin A. Moser and Gabor Tardos, A constructive proof
of the general Lovasz Local Lemma, arXiv
Robin A. Moser, A constructive proof
of the Lovasz Local Lemma, STOC 2009 Best Paper Award
Joel Spencer, Robin Moser makes
Lovasz Local Lemma Algorithmic!
Terrence Tao, Moser's entropy
compression argument
Facility
Location
J.H.
Lin and J. Vitter, Approximation
algorithms for geometric median problems, IPL 1992
D.
Shmoys, E. Tardos, and
K. Aardal, Approximation algorithms for facility location problems, STOC 1997
R. Mettu and
C.G. Plaxton, The
Online Median Problem, SICOMP 2003