Princeton University logo
Princeton University
Computer Science Department

Computer Science 594
Limits on Approximation
  Moses Charikar

  Spring 2007

Course Summary

In this course, we will explore limits on approximation algorithms in various forms - hardness result for problems based on different kinds of complexity assumptions, as well as integrality gap constructions showing limitations for LP and SDP approaches. Recent results seem to indicate a close connection between the two. We will read recent papers showing hardness of approximation for various basic problems in constraint satisfaction and network design. We will explore the Unique Games Conjecture and hardness results based on this. We will also study lift and project systems - systematic procedures to construct strengthened LP and SDP relaxations and study recent results showing limitations on such approaches. Enroute, we will also see the best known aproximation problems for the problems we will study.

This is a seminar course with no homework exercises. Participants will be expect to present papers and possibly scribe lecture notes.

Administrative Information

Lectures: Tue Thu 3:00-420   Room 401, CS Bldg.

Professor: Moses Charikar - 305 CS Building - 258-7447 moses [AT]
                  Office hours by appointment

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml [AT]


Lecture outlines and readings

  1. Feb 6  Introduction. p-center problem, set cover, asymmetric p-center
  2. Feb 8  Asymmetric p-center continued. Introduction to PCP, Label Cover.

  3. Feb 13  Parallel repetition, Hardness of Set Cover.

  4. Feb 15  Hardness of Hypergraph Vertex Cover.

  5. Feb 20  Proofs of Combinatorial Lemmas and preparation for asymmetric p-center hardness
  6. Feb 22  Hardness of  asymmetric p-center
  7. Feb 27  Generalizations of Steiner tree: Priority Steiner tree and Cost-Distance
  8. Mar 1  Algorithm for Cost-Distance and begin Hardness of Priority Steiner tree and Cost-Distance
  9. Mar 6  (Class starts at 2:30) Hardness of Priority Steiner tree and Cost-Distance contd.
    (please review set cover construction covered in the previous class)
  10. Mar 8  Edge Disjoint Paths and Congestion
  11. Mar 13  (Class starts at 2:30) Undirected Edge Disjoint Paths and Congestion
    finish integrality gap and start hardness result
  12. Mar 15  Directed Edge Disjoint Paths and Congestion
  13. Mar 27  Directed Multicut: integrality gaps and hardness
  14. Mar 29  Jan Vondrak: Introduction to Fourier Analysis

  15. Apr 3  Seshadhri Comandur: The Unique Games Conjecture
  16. Apr 5  Konstantin Makarychev: UGC based Hardness of Max-Cut
  17. Apr 10  David Steurer: UGC based Hardness of Multicut and Sparsest Cut
  18. Apr 12  Indraneel Mukherjee: Hardness results based on Feige's Random 3SAT hypothesis
  19. Apr 17  Continuation of David and Indraneel's presentations from last week

  20. Apr 19  No class

  21. Apr 24  Wolfgang Mulzer: Lift and Project methods for Max Cut
  22. Apr 26  Yury Makarychev: Lift and Project methods for Vertex Cover
In the coming weeks ...

Related Courses and Resources