Approximation Algorithms Seminar - Fall 2001/2

Related Books:

• "Approximation Algorithms" by Vijay Vazirani.
• "Approximation Algorithms for NP-Hard Problems" by Dorit Hochbaum.

Lectures Schedule:

• Lecture 1 (1/11/01) : Yair Bartal: Introduction.
  • Introduction to the field.
    
  • Min-TSP and min Steiner tree.
    
  • Vertex Cover.
    
  • Set Cover.
  
  
• Lecture 2 (8/11/01) : Gil Shallom: Local Ratio.
  • The local ratio method for covering problems [Bar-Yehuda].
  
  
• Lecture 3 (18/11/01) : Dan Gutfreund: Randomized Rounding.
  • LP based approximation for MAXSAT [Goemans Williamson].
  
  
• Lecture 4-5 (22+29/11/01) : Eyal Rozenman: Primal-Dual.
  • The primal-dual method [Goemans Williamson].
  • Primal-dual based approximation for constrained forest problems [Goemans Williamson].
  
  
• Lecture 5 (6/12/01) : Ahuva Mualem: Min Multicut.
  • Approximating min-multicut [Garg Vazirani Yannakakis].
  
  
• Lecture 6 (13/12/01) : Ron Lavi: Facility location and k-median.
  • On the facility location and the k-median problems [Jain Vazirani].
  
  
• Lecture 7 (20/12/01) : Hana Chockler: Semidefinite Programming - MAXCUT.
  • SDP based approximation for MAXCUT [Goemans Williamson].
  
  
• Lecture 8 (27/12/01) : Yonatan Bilu: Semidefinite Programming - Coloring.
  • SDP based approximation for min graph coloring [Karger Motwani Sudan].
  
  
• Lecture 9 (3/1/02) : Liad Blumrosen: Approximation in a Non-cooperative Game.
  • How Bad is Selfish Routing ? [Roughgarden Tardos].
  • Designing Networks for Selfish Users is Hard [Roughgarden].
  
  
• Lecture 10 (10/1/02) : Rica Gonen: Unsplittable flow.
  • Unsplittable flow [Azar Regev].