Tentative Calendar
| Week | Topic | Handouts |
Scribe |
Suggested
Reading |
| Sep 7 |
Administrivia; Review
of basics, introduction to approximation algorithms Warm-up with set cover: Greedy algorithm; applications LINEAR PROGRAMMING: Introduction and the geometry of LP |
ApproxAlgs |
Rajmohan Rajaraman |
Vazirani, Ch
1, 2 |
| Sep 11, 14 |
LP-duality: The weak and strong duality theorems |
IntroToLP LPGeometryDuality |
Eric Robinson |
Vazirani, Ch
12 Goemans notes on LP |
| Sep 18, 21 |
Randomized and deterministic rounding Filtering technique Case study: Facility Location Shmoys-Tardos-Aardal algorithm |
RandomizedRounding IntroToFacilityLocation |
San Tan |
Lin-Vitter Shmoys-Tardos-Aardal |
| Sep 25, 28 |
Case study: Facility
Location Analysis via dual-fitting and local search Mettu-Plaxton & Arya et al algorithms |
Problem
Set 1 FacilityLocationFiltering FacilityLocationDualFitting |
Bishal Thapa |
Mettu-Plaxton Archer et al Arya et al Korte-Vygen, Ch 22 |
| Oct 2, 5 |
Wrap up local search analysis The primal-dual schema |
KMedian PrimalDualIntro |
Jian Wen |
Goemans-Williamson Vazirani, Ch 15 |
| Oct 9, 12 |
Case study: Network
design Goemans-Williamson algorithm for Steiner forest |
SteinerForest SteinerNetworkIntro |
Laura Poplawski |
Goemans-Williamson Jain Vazirani, Ch 22, 23 Korte-Vygen, Ch 20 |
| Oct 16, 19 |
Case study: Network design, contd Jain's algorithm for Generalized Steiner Network |
SteinerNetwork1
SteinerNetwork2 |
Hooman Javaheri |
Jain Vazirani, Ch 22, 23 Korte-Vygen, Ch 20 |
| Oct 23, 26 |
Case study: Multicommodity Flow & Sparsest cut Leighton-Rao algorithm |
UniformMCF1 UniformMCF2 |
Zhifeng Sun |
Leighton-Rao Vazirani, Ch 21 |
| Oct 30, Nov 2 |
Primal-dual approximation scheme for multicommodity flow SEMI-DEFINITE PROGRAMMING (SDP): Shannon's theory of information Shannon capacity of a graph |
Problem
Set 2 MCFApprox InformationTheory |
Emrah Bayraktaroglu |
Young Garg-Konemann Korte-Vygen, Sec 19.2 Shannon |
| Nov 6, 9 |
Semi-definite programs Case study: Shannon capacity of the Pentagon |
Pentagon Intro to SDP |
Jingjing Duan |
Lovasz notes Goemans-Williamson |
| Nov 13, 16 |
Rounding SDPs Case study: Max-Cut Case study: Sparsest cut |
Max Cut Sparsest Cut |
Abhishek Chaubey |
|
| Nov 20 |
Case study: Sparsest cut Metric Embeddings and applications Bourgain's Theorem |
Sparsest Cut, contd. |
Tao Jin |
|
| Nov 27, 30 |
Case
study: Sparsest cut, contd Arora-Rao-Vazirani algorithm |
ARV algorithm ARV contd Sample Solution to PS1 Problem Set 3 |
Shahzad Rajput Stefan Savev |
|
| Dec 4, 7 |
PROBABILISTIC
TECHNIQUES BPP and PH Lower bound for volume estimation Case study: HITS algorithm and Google's Pagerank |
Probabilitic1 Probabilistic2 |
Max Bandazian Xin Dong |
|
| Dec 11, 14 |
Student presentations | Sample
Solution to PS2 Sample Solution to PS3 |
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.
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