CSE 522, Autumn 2009: Approximation Algorithms

This quarter we will study the design and analysis of approximation algorithms for NP-hard problems, specifically approximation algorithms based on linear and semidefinite programming. For at least half the course we will be using a new, unpublished book by David Williamson and David Shmoys that I will be handing out in class.

I am definitely planning on covering most of chapter 1, Sections 6.1, 6.2, 7.1-7.4, 8.3-8.6, 11.2, and chapter 15. If time permits, I will cover other portions of Chapter 6, 8, 13 and 15.

I am working on a list of open problems. It is very much under construction.

Administrivia

• Instructor: Anna Karlin. Office hours by appointment.
• Class meets Mondays and Thursdays, from noon to 1:20pm, in CSE 203.
• Expectations from students.
• A couple of copies of the Williamson/Shmoys book are available in the theory lab, CSE 306. Please do not remove those copies (except for quickly making copies). There are also other books on approximation algorithms in the theory lab library for your browsing pleasure.

---

Lecture topics with readings, references and, occasionally, lecture notes:

• October 1: Administrivia, introduction to techniques via example of Set Cover, review of some linear programming basics.
  • Williamson and Shmoys, Chapter 1.
  • Williamson and Shmoys, Appendix on linear programming
  • Other references on linear programming:
    • Michel Goemans lecture notes
    • Jeff Erickson's lecture notes
    • "Understanding and Using Linear Programming", book by Matousek and Gartner.
    • "Linear Programming", book by Chvatal.
    • "Linear Programming", book by Howard Karloff.
• October 5: Introduction to iterated rounding
  • Mohit Singh's Ph.D. Thesis: Chapter 2 and Sections 3.1 and 3.2
• October 8: More iterated rounding -- an additive +1 approximation algorithm for degree-constrained minimum spanning trees
  • Williamson and Shmoys, Section 11.2
  • Mohit Singh's Ph.D. Thesis: Chapter 4.
• October 12: Finish iterated rounding.
• October 15: NO CLASS
• October 19: Primal-dual algorithms - feedback vertex set and generalized Steiner Tree problem.
  • Williamson and Shmoys, Sections 7.3-7.4
• October 22: Finish primal-dual algorithms. Start metric methods - GVY algorithm for multicut.
• October 26: Finish GVY algorithm for multicut. Motivate tree metrics with Buy-at-Bulk Network Design.
  • Williamson and Shmoys, Sections 8.3-8.4, 8.6.
• October 29: Fakcharoenphol, Rao and Talwar's algorithm for probabilistic approximation of metrics by tree metrics.
  • Williamson and Shmoys, Sections 8.5
  • Fakcharoenphol, Rao and Talwar's paper
• Nov 2: Racke's work on optimal hierarchical decompositions for congestion minimization in networks.
  • Williamson and Shmoys, Sections 15.2-15.3
  • Racke's paper
• November 6: Finish Racke's work on optimal hierarchical decompositions for congestion minimization in networks, and his log approximation for bisection. Go over presentation of result by Andersen and Feige.
  • Andersen/Feige paper
• November 9: Guest lecture by R. Ravi on iterative methods.
  • Survey by R. Ravi on iterative methods
• November 12: Guest lecture by Niv Buchbinder on online primal-dual algorithms and the k-server problem.
  • Survey by Buchbinder and Naor on online primal-dual
• November 16: NO CLASS
• November 19: NO CLASS
• November 23: Intro to SDP. Goemans/Williamson.
  • Survey by Buchbinder and Naor on online primal-dual
• November 30: Intro to sparsest cut.
  • Williamson and Shmoys, Section 15.1
  • Survey by Shmoys in book edited by Hochbaum on Approximation Algorithms
• December 3: ARV algorithm for sparsest cut.
  • Survey by Arora, Rao and Vazirani on Geometry, Flows and Graph-Partitioning
  • Expander Flows, Geometric Embeddings and Graph Partitioning by Arora, Rao and Vazirani
  • James Lee paper giving proof of the big core theorem (Section 4 and 5)
• December 10: Finish ARV

• Student presentations December 7 - December 17, all in CSE 203. All the abstracts
  • Fri, Dec 11, 9:30am: Mathias Hallman
  • Fri, Dec 11, 10:30am: Thach Nguyen
  • Fri, Dec 11, 1pm: Jessica Chang
  • Fri, Dec 11, 2pm: Ben Birnbaum
  • Mon, Dec 14, 10am: Kate Moore
  • Mon, Dec 14, 11am: Kevin Zatloukal
  • Mon, Dec 14, 12pm: Richard Pang
  • Mon, Dec 14, 1:30pm: Elisa Celis
  • Mon, Dec 14, 2:30pm: Alyssa Harding
  • Tues, Dec 15, 1:00pm: Adrian Sampson
  • Wed, Dec 16, 9am: Karthik Mohan
  • Wed, Dec 16, 10am: Austin Webb
  • Thurs, Dec 17, noon: Trinh Huynh-Ngoc