CS 7880: Topics in Theories of Computer Science

Algorithmic Power Tools

Fall 2009

Tentative Calendar
 Week  Topic Handouts
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
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
Oct 20, 23
Primal-dual framework: set cover
Primal-dual framework: Steiner Forest
Primal-Dual and Steiner Forest

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
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
Dec 1, 4
Multiplicative-update: Multicommodity flow
No class on Friday
Scott Roche
Dec 8, 11
Hierarchical decompositions and oblivious routing
Abutalib Aghayev
Dec 15, 18
Student presentations

 For the scribe notes, here are the latex 2e macros files (and the latex source for the first lecture as a sample)



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

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

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

K. Jain and V. Vazirani, Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, JACM 2001

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