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] cs.princeton.edu
                  Office hours by appointment

Graduate Coordinator: Melissa Lawson - 310 CS Building - 258-5387 mml [AT] cs.princeton.edu

CLICK HERE TO JOIN THE MAILING LIST FOR THIS  CLASS.

Lecture outlines and readings

1. Feb 6  Introduction. p-center problem, set cover, asymmetric p-center
   
   • An O(log*n) Approximation Algorithm for the Asymmetric p-Center Problem
     Rina Panigrahy and Sundar Vishwanathan
     
     
2. Feb 8  Asymmetric p-center continued. Introduction to PCP, Label Cover.
   
   
3. Feb 13  Parallel repetition, Hardness of Set Cover.
   
   • See Lecture 3 of Georgia Tech course or Lectures 14 and 15 of U.Washington course
     
   • Further reading:
     Parallel repetition: simplifications and the no-signaling case,
     Thomas Holenstein
     
   
   
4. Feb 15  Hardness of Hypergraph Vertex Cover.
   
   • Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-eps)
     Irit Dinur, Venkatesan Guruswami, Subhash Khot
     (Read Sections 1-3)
     
   
   
5. Feb 20  Proofs of Combinatorial Lemmas and preparation for asymmetric p-center hardness
   
   • Combinatorial proofs were from
     A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
     Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
     (Section 2.1)
     
     
6. Feb 22  Hardness of  asymmetric p-center
   
   • Asymmetric k-center is log^*n-hard to Approximate
     Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, and Seffi Naor
     
     
7. Feb 27  Generalizations of Steiner tree: Priority Steiner tree and Cost-Distance
   
   • Resource optimization in QoS multicast routing of real-time multimedia
     Moses Charikar, Seffi Naor, Baruch Scheiber
     (Section 3)
   • Cost-Distance: Two metric network design
     Adam Meyerson, Kamesh Munagala, Serge Plotkin
     (Sections 2-4)
     
     
8. Mar 1  Algorithm for Cost-Distance and begin Hardness of Priority Steiner tree and Cost-Distance
   
   • On the approximability of some network design problems
     Julia Chuzhoy, Anupam Gupta, Seffi Naor, Amitabh Sinha
     
     
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)
   
   • On the approximability of some network design problems
     Julia Chuzhoy, Anupam Gupta, Seffi Naor, Amitabh Sinha
     
     
10. Mar 8  Edge Disjoint Paths and Congestion
    
    • New Hardness Results for Undirected Edge-Disjoint Paths.
      Julia Chuzhoy, Sanjeev Khanna
      (See integrality gap construction in Section 4)
      
      
11. Mar 13  (Class starts at 2:30) Undirected Edge Disjoint Paths and Congestion
    finish integrality gap and start hardness result
    
    • New Hardness Results for Undirected Edge-Disjoint Paths.
      Julia Chuzhoy, Sanjeev Khanna
      hardness result for congestion 1 from the earlier paper:
      
    • Hardness of the undirected edge-disjoint paths problem
      Matthew Andrews, Lisa Zhang
      
      
12. Mar 15  Directed Edge Disjoint Paths and Congestion
    
    • Hardness of directed routing with congestion
      Julia Chuzhoy and Sanjeev Khanna
    • Scribe notes by Rajsekar Manokaran (unedited).
      
      
13. Mar 27  Directed Multicut: integrality gaps and hardness
    
    • Julia Chuzhoy (joint work with Sanjeev Khanna, to appear in STOC 2007)
      
      
14. Mar 29  Jan Vondrak: Introduction to Fourier Analysis
    
    
15. Apr 3  Seshadhri Comandur: The Unique Games Conjecture
    
    • On the power of unique 2-prover 1-round games
      Subhash Khot
      
      
16. Apr 5  Konstantin Makarychev: UGC based Hardness of Max-Cut
    
    • Optimal inapproximability results for MAX-CUT and other two-variable CSPs?
      S. Khot, G. Kindler. E. Mossel, R. O'Donnell.
      
      
17. Apr 10  David Steurer: UGC based Hardness of Multicut and Sparsest Cut
    
    • On the Hardness of Approximating Multicut and Sparsest-Cut
      Shuchi Chawla, Robi Krauthgamer, Ravi Kumar, Yuval Rabani and D. Sivakumar
      
      
18. Apr 12  Indraneel Mukherjee: Hardness results based on Feige's Random 3SAT hypothesis
    
    • Relations between average case complexity and approximation complexity
      Uri Feige
      
      
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
    
    • Linear Programming Relaxations of Maxcut
      Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu
      
      
22. Apr 26  Yury Makarychev: Lift and Project methods for Vertex Cover
    
    • Tight Integrality Gaps for Lovasz-Scrijver LP Relaxations of Vertex Cover and Max Cut
      Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
      
      

• Buy-at-bulk (general case) - algorithms and hardness
  
  • Hardness of buy-at-bulk network design
    Matthew Andrews
  • Approximation Algorithms for Non-uniform Buy-at-Bulk Network Design Problems
    Chandra Chekuri, MohammadTaghi Hajiaghayi, Guy Kortsarz and Mohammad Salavatipour
    
    
• Hardness of edge disjoint paths and congestion
  
  • An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow
    Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
  • Hardness of the undirected edge-disjoint paths problem with congestion
    Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang.
    
  • Hardness of directed routing with congestion
    Julia Chuzhoy and Sanjeev Khanna
  • Hardness of low congestion routing in directed graphs
    Venkat Guruswami and Kunal Talwar
    
    
• (optional) "Metric" problems: metric labeling and 0-extension
  
  • Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields
    Jon Kleinberg and Eva Tardos
    
  • An improved approximation algorithm for the 0-extension problem
    Jittat Fakcheroenphol, Chris Harrelson, Satish Rao, Kunal Talwar
    
  • The Hardness of Metric Labeling
    Julia Chuzhoy and Seffi Naor
    
  • On Earthmover Distance, Metric Labeling, and 0-Extension
    Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani
  
  
• Alternate hardness hypotheses: Unique Games Conjecture and hardness consequences for Max-Cut and Sparsest Cut
  
  • On the power of unique 2-prover 1-round games
    Subhash Khot
  • Optimal inapproximability results for MAX-CUT and other two-variable CSPs?
    S. Khot, G. Kindler. E. Mossel, R. O'Donnell.
  • On the Hardness of Approximating Multicut and Sparsest-Cut
    Shuchi Chawla, Robi Krauthgamer, Ravi Kumar, Yuval Rabani and D. Sivakumar
  • The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into L1
    Subhash Khot, Nisheeth Vishnoi
    
  • Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems
    Nikhil Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi
    
    
• Alternate hardness hypotheses: Feige's random 3CNF hypothesis and consequences
  
  • Relations between average case complexity and approximation complexity
    Uri Feige
    
    
• Lift-and-Project systems: negative results for Vertex Cover and Max Cut
  
  • Linear Programming Relaxations of Maxcut
    Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu
  • Tight Integrality Gaps for Lovasz-Scrijver LP Relaxations of Vertex Cover and Max Cut
    Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
  • Tight Integrality Gaps for Vertex Cover SDPs in the Lovasz-Scrijver hierarchy
    Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis
    

Related Courses and Resources

• PCP and Hardness of Approximation, Luca Trevisan (UC Berkeley), Spring 2006.
• The PCP Theorem and Hardness of Approximation, Venkat Guruswami and Ryan O'Donnell (U. Washington), Autumn 2005.
  
• Probabilistically Checkable Proofs and Hardness of Approximation, Subhash Khot (GeorgiaTech), Spring 2004.

• Analysis of Boolean Functions, Ryan O'Donnell (CMU) Spring 2007.
  
  
• The NP-Completeness Column: The Many Limits on Approximation, David S. Johnson, ACM Transactions on Algorithms (TALG) 2(3):473-489 (July 2006)