- 05/18.Check out the following survey reports: (wisc.edu access only)
Online optimization algorithms [PDF] by Dave Andrzejewski
Bounds on alphabet size and rate for network coding [PDF] by Siddharth Barman
Network coding [PDF] by Matt Elder
Stochastic optimization [PDF] by Chi Man Liu
- 05/10. The final exam [PDF] is available now. It is due by midinght on May 15.
- 05/10. You can now download all the scribe notes in a single PDF. See below.
The field of approximation algorithms has developed in
response to the difficulty in solving a good many optimization
problems exactly. This course will present general techniques
that underly these algorithms. Read more ...
Scribe notes & readings
Here are all the scribe notes in one file: [PDF]
- (1/23) Intro, vertex cover, TSP. [PDF]
- (1/25) Steiner tree, Greedy approximations: multiway cut. [PDF]
- (1/30) Greedy approximations: set cover, makespan. [PDF]
- (2/1) Edge disjoint paths, DP-based algorithms: FPTAS for knapsack. [PDF]
Chekuri and Khanna's paper on EDP
- (2/6) Bin-packing, Euclidean TSP. [PDF]
- (2/8) Euclidean TSP (contd.) [unedited PDF]
Lecture notes by Michel Goemans
- (2/13) Local search: max-cut, facility location [PDF]
Korupolu et al.'s paper for facility location. Arya et al.'s improved analysis.
Survey by David Shmoys on algorithms for k-median and facility location.
- (2/15) Facility location (contd.), min degree spanning tree [PDF]
Furer and Raghavachari's paper on min degree spanning trees.
- (2/20) Linear Programming [PDF]
- (2/22) LP rounding: vertex cover, facility location (see lect 9 & 11 for notes)
- (2/27) Facility location (contd.), Randomized rounding: set cover, routing [PDF]
Shmoys, Tardos and Aardal's paper on LP-rounding for facility location.
Lecture notes on Chernoff bounds and min-congestion routing.
- (2/29) min-congestion routing (contd.), LP duality and the primal-dual method [PDF]
Raghavan and Thompson's paper introducing randomized rounding.
Survey by David Williamson on the primal-dual method.
- (3/6) Primal-dual: Vertex cover, Steiner forest [PDF]
- (3/8) Primal-dual: Steiner forest (contd.), facility location [PDF]
- (3/13) Facility location (contd.); Cut LPs and metrics [PDF]
- (3/15) Multiway cut, Multicut via region growing [PDF]
Survey by David Shmoys on multicut, sparsest cut, and their applications.
The original multicut paper by Garg, Vazirani and Yannakakis.
- (3/20) Sparsest Cut, Balanced cut: O(log k log D)-approx [PDF]
- (3/21) Balanced Cut (contd.), Sparsest Cut & embeddings into ell_1 [PDF]
For more applications of sparsest cut and balanced cut, see the survey by David Shmoys
- (3/22) Bourgain's embedding into ell_1, Semi-Definite Programming [PDF]
This paper by Linial, London & Rabinovich has a number of nice theorems about embeddings apart from the approximation to sparsest cut.
- (3/27) SDP: Max-cut, max-2-SAT [PDF]
A really good survey by Helmberg on the techniques for solving SDP and its applications to NP-hard optimization problems.
For more on the theory of SDP and SDP duality, see this survey by Vandenberghe and Boyd.
Goemans and Williamson's max-cut paper.
- (3/29) SDP: Coloring [PDF]
Karger, Motwani & Sudan's paper, and Blum & Karger's improvement.
- (3/30) Approximation via tree embeddings [PDF]
- (4/10) Low diameter partitioning, and approximating metrics by tree metrics [PDF]
Bartal's second paper on embeddings into trees, and the FRT optimal result.
- (4/12) Approximate counting, sampling [PDF]
A very nice set of lecture notes by Mark Jerrum.
- (4/24) Markov Chain Monte Carlo, random walks and mixing [PDF]
Survey on rapid mixing by Jerrum and Sinclair including conductance and the canonical paths argument. Chapter on coupling by Jerrum.
- (4/26) MCMC contd. and Lagrangean techniques [PDF1 and PDF2]
- (4/27) Inapproximability [PDF]
- (5/1) PCPs and hardness of approximating Max3SAT [PDF]
- (5/3) Hardness of approximating set cover [PDF]
(Solutions are not available any more. Sorry!)
- HW1 [PDF] [Solutions]
- HW2 [PDF] [Solutions]
- HW3 [PDF] [Solutions]
Project ideas are available here.
A template for scribe notes can be found here.
Before scribing lectures, please read this
note on mathematical writing by Knuth, Larrabee and Roberts.