15-854 Approximation and Online Algorithms

Instructor: Avrim Blum

MW 1:30-2:50. Wean 4615A. 12 Units

Course information and syllabus
Rough schedule and ideas for presentation topics
The final exam is now available. When you are ready to take it, click here.

Assignments

Lecture Notes

Please feel free to send me email if you notice any mistakes.

  1. 01/19:Intro. Examples: Vertex Cover, rent or buy, pursuer/evader. Reading: section 2 of Shmoys. See also: Goemans intro, Rabani notes on VC.
  2. 01/24:Set-cover: greedy and randomized rounding. p-center problem (symmetric and asymmetric). Reading: [Panigrahy-Vishwanathan '98]. See also: Williamson lecture 2, Cheriyan-Ravi notes on set-cover, center & median problems.
  3. 01/26:Conditional expectation method and randomized rounding: MAX-SAT and routing problems. Related readings: Williamson lecture 5, Shmoys section 3, Rabani notes.
  4. 01/31:Continuing with above. Also, a little about approximation hardness. Additional reading: Shmoys section 1, Goemans section 2.
  5. 02/02:A little more on approx hardness, PTAS and FPTAS. More details on Clique hardness. Additional reading: Williamson lecture 3.
  6. 02/07:The shortest common superstring problem. We will be discussing work in BJLTY 1991. Latest results in Sweedyk 1999/2000. The longest path song and lyrics.
  7. 02/09:The MAX-CUT problem and Semidefinite Programming. Additional reading: Williamson lecture 6, Goemans section 5.
  8. 02/14:SDPs for approximate 3-coloring. Additional reading: Williamson lecture 7 (only proves the simpler version). Here is the KMS paper and the most recent bound.
  9. 02/16:Random projections and approximate nearest neighbor.
  10. 02/21:Approximating metric spaces with (heirarchical) tree metrics. Application to "buy at bulk network design".
  11. 02/23:L_1 embeddings, Bourgain's theorem, and balanced separators. Additional reading: Cheriyan-Ravi Chapter 11.
  12. 02/28:PCP and approximation hardness (Jochen Könemann). Here are some more notes on the topic.
  13. 03/01:On line algorithms: list update and paging. Additional reading: Goemans sections 1-4. Borodin and El-Yaniv Chapters 1 and 3.
  14. 03/08:Paging: deterministic and randomized. Intro to k-server problem. Additional reading: Borodin and El-Yaniv Ch 3,4.
  15. 03/13:Intro to k-server. The Metrical Task System Problem (det and randomized). Additional reading: Borodin and El-Yaniv Ch 9, 10.1-10.3
  16. 03/15:On-line machine learning. Combining "expert" advice. Application to combining online algorithms and proof of min-max. Here is a related survey paper.
  17. 03/20:On-line learning contd + portfolio selection.
  18. 03/22:On-line search and navigation.
  19. 04/03:On-line load balancing and virtual circuit routing. See also Borodin and El-Yaniv Ch 12.1-12.3 and the survey by Yossi Azar.
  20. 04/05:Decision theories and metrics for online algorithms [Pat Riley and Elly Winner]
  21. 04/10:Faster exact algorithms for 3-SAT and 2nd half [Ioannis Koutis and Ke Yang]
  22. 04/12:PTASs for dense instances of NP-hard problems. first half, second half. [Amitabh Sinha and Marcio Palmeira]
  23. 04/17:The Primal-Dual method [Martin Zinkevich and Eric Bauer] See also Williamson's notes.
  24. 04/19:The k-server problem [Avrim Blum]. See the latest paper by Koutsoupias.
  25. 04/24: Online learning and the Winnow algorithm [Leejay Wu and Greg Schohn]
  26. 04/26: minimizing OBDDs [Sanjit Seshia]
  27. 05/01: Online scheduling [Nikhil Bansal and Bianca Schroeder]
  28. 05/03: Edge-dominating sets [Ojas Parekh]. See also this paper. General wrap-up [Avrim Blum]

Handouts and Readings

Research papers and related lecture notes. David Williamson's notes probably best tracks the material we will cover in the approximation portion of the course.
Avrim Blum
Last modified: Sat May 13 19:03:28 EDT 2000