Tentative Calendar
| Week | Topic | Handouts |
Scribe |
Suggested
Reading |
| Sep 11 |
Overview of course Intro: NP-completeness & 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 |
Alon-Spencer, Ch 1-5 |
| Sep 22, 25 |
Proof of LLL and example applications Application of LLL to packet routing |
General
LLL & Applications Packet Routing |
Eric Miles Dimitrios Kanoulas |
Leighton-Maggs-Rao |
| Sep 29, Oct 2 |
Constructive proof of LLL The counting argument Entropy compression argument |
Harsh Chamarthi |
Moser Moser-Tardos 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 Dual-fitting analysis: Facility location |
Problem Set 1 Facility Location: Filtering Facility Location: Dual-Fitting |
Lin-Vitter Shmoys-Tardos-Aardal Mettu-Plaxton |
|
| Oct 20, 23 |
Primal-dual framework: set cover Primal-dual framework: Steiner Forest |
Primal-Dual and Steiner Forest
|
Goemans-Williamson 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 | Fakcharoenphol-Rao-Talwar |
|
| Nov 24 |
Multiplicative-update: Online learning |
Scott Roche |
Arora-Kale-Hazan |
|
| Dec 1, 4 |
Multiplicative-update: Multicommodity flow No class on Friday |
Scott Roche |
Garg-Konemann Young |
|
| Dec 8, 11 |
Hierarchical decompositions and oblivious routing |
Abutalib Aghayev |
Racke |
|
| Dec 15, 18 |
Student presentations |
References
Books
Vijay Vazirani, Approximation Algorithms,
Springer-Verlag,
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 Facility
Location J.-H.
Lin and J. Vitter, Approximation
algorithms for geometric median problems, IPL 1992 R. Mettu and
C.G. Plaxton, The
Online Median Problem, SICOMP 2003
F.T. Leighton, B. Maggs, and S. Rao, Packet routing and
job-shop 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
D.
Shmoys, E. Tardos, and
K. Aardal, Approximation algorithms for facility location problems, STOC 1997
V. Arya, N. Garg, R. Khandekar, A. Meyerson, K.
Munagala, and V.
Pandit, Local Search
Heuristics for k-Median and Facility Location Problems, SICOMP 2004
A.
Archer, R. Rajagopalan and D. B. Shmoys, Lagrangian relaxation for the k-median problem: new insights and
continuity properties, ESA 2003
Network
Design
M. Goemans and G. Williamson, A
General Approximation Technique for Constrained Forest
Problems, SIAM Journal on Computing, 24, 296--317, 1995.
M.X. Goemans and D.P. Williamson, The
Primal-Dual Method for Approximation Algorithms and its Application to
Network Design Problems, in Approximation Algorithms, D.
Hochbaum, Ed., 1997.
K. Jain, A Factor 2
Approximation Algorithm for the Generalized Steiner Network Problem.
Combinatorica 21(1): 39-60 (2001)
Metric Embeddings and Oblivious Routing
J. Fakcharoenphol, S. Rao, and K. Talwar,
A tight bound
on approximating arbitrary metrics by tree metrics, STOC 2003
H. Racke,
Optimal
hierarchical decompositions for congestion minimization in
networks, STOC 2008, Best Paper award.
Multicommodity Flow and Sparsest Cut
T.
Leighton and S. Rao, Multicommodity
max-flow min-cut theorems and their use in designing approximation
algorithms, JACM 1999
N. Young, Randomized rounding without solving the
linear program, SODA 1995
N. Garg and J. Konemann, Faster and
Simpler Algorithms for Multicommodity Flow and Other Fractional Packing
Problems, FOCS 1998
Information Theory and Shannon capacity
C.
E. Shannon, ``A
mathematical theory of communication,'' Bell System Technical
Journal, vol. 27, pp. 379-423 and 623-656, July and
October, 1948.
C. E. Shannon, ``The Zero Error Capacity of a
Noisy Channel,'' Institute of
Radio Engineers, Transactions on Information Theory, Vol. IT-2
(September, 1956), pp. S8-S19.
Reprinted in
D. Slepian, editor, Key Papers in the Development of Information
Theory,
IEEE Press, NY, 1974.
Included in Part A.
S. Arora, S.
Rao, and U. Vazirani, Expander Flows,
Geometric Embeddings and Graph Partitioning, STOC 2004
Semi-Definite Programming
L. Lovász, Semidefinite programs and combinatorial
optimization (Lecture notes) (1995)
M. Goemans and D. Williamson, Improved
Approximation Algorithms for Maximum Cut and Satisfiability Problems
Using Semidefinite Programming, JACM 1995
S. Arora, S. Rao,
and U. Vazirani, Expander
Flows, Geometric Embeddings and Graph Partitioning, STOC 2004