Approximation Algorithms Seminar

Moses Charikar

This is a weekly seminar focused on approximation algorithms. Initial meetings will be devoted to building background material and in later meetings, we will read recent papers in the area.

Time: Wednesday, 10:30 am Location: CS 302

Mailing list for announcements:

• Subscribe to approx-seminar.
• [Feb 8] Introduction to approximation algorithms, and some intriguing open problems.
  • Vertex cover
  • Max acyclic subgraph
  • Scheduling unit time jobs
  • TSP
• [Feb 15] LP relaxations, duality and lagrangean relaxation
  • I will present the paper:
    Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, Kamal Jain and Vijay V. Vazirani, Journal of the ACM (JACM, Volume 48 , Issue 2 (March 2001), pages: 274 - 296
  • Background reading on LP duality and rounding techniques:
    David Williamson's lecture notes on set cover.
  • Facility location and k-median are covered in lecture 9 and lecture 10 of David Williamson's notes on Approximation algorithms.
• [Feb 22] Cut problems, metric methods, divide and conquer
  • I talked about metric methods, specifically about multicut and balanced cut.
  • For background, see the notes from lecture 11 in David Williamson's notes on Approximation algorithms.
• [Mar 1] spreading metrics, divide and conquer
  • I will talk about uses of cut procedures in divide and conquer algorithms, specifically in minimum linear arrangement and feedback arc set.
  • For background, see the notes above.
• [Mar 8] Introduction to SDP: max cut and graph coloring
  • See the original papers by Goemans-Williamson and Karger-Motwani-Sudan:
  • Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Michel Goemans and David Williamson, Journal of the ACM (JACM), Volume 42, Issue 6 (November 1995), Pages: 1115 - 1145.
  • Approximate graph coloring by semidefinite programming, David Karger, Rajeev Motwani and Madhu Sudan, Journal of the ACM (JACM), Volume 45, Issue 2 (March 1998), Pages: 246 - 265.
• [Mar 15] Eddie
  • New Approximation Guarantees for Chromatic Number, to appear in STOC 2006.
• [Mar 29] primal-dual algorithms for connectivity
  • See Sections 7.1-7.4 of draft Approximation Algorithms text
  • Chapter by Goemans and Williamson in Hochbaum's book.
• [Apr 5] No seminar (Moses out of town)
• [Apr 12] Mohammad
  • Distance approximation by HSTs
  • A tight bound on approximating arbitrary metrics by tree metrics,
    Jittat Fakcharoenphol, Satish Rao, Kunal Talwar, STOC 2003 and JCSS 2004.
  • Also see Approximating Metrics by Tree Metrics (survey),
    SIGACT news Algorithms column, Volume 35 , Issue 2, 2004.
• [Apr 19] Approximation schemes for geometric problems
  • See Sanjeev's survey. This survey accompanied a semiplenary talk at ISMP and appeared in Math Programming, 97 (1,2) July 2003.
  • This is a precursor to Wolfgang's presentation next week on a paper on min-weight triangulation (in STOC 2006).

Possible topics for future weeks

• Primal dual method
  • generalized steiner tree
• iterative rounding
  • survivable network design
• local search
  • k-median
  • facility location via dual fitting
• cost sharing schemes
  • stochastic optimization
• SDP methods
  • Max Cut
  • Coloring
  • l_2^2 metrics
• Dynamic programming
  • Knapsack
  • Eucidean TSP
  • Minimum triangulation in the plane
• Tree approximations
  • distance approximation by HSTs
  • distance approximation by spanning trees
  • capacity approximation by tree decomposition

Suggestions for presentations

• Minimum triangulation [Wolfgang]
  • A quasi-polynomial time approximation scheme for minimum triangulation,
    Jan Remy and Angelika Steger, to appear in STOC 2006.
• Distance approximation by spanning trees
  • Lower-Stretch Spanning Trees,
    M. Elkin, Y. Emek, D. Spielman, and S. Teng, STOC 2005.
  • Improved Embedding of Graph Metrics into Random Trees
    Kedar Dhamdhere, Anupam Gupta, Harald Racke, SODA 2006.
• Distance approximation by HSTs [Mohammad]
  • A tight bound on approximating arbitrary metrics by tree metrics,
    Jittat Fakcharoenphol, Satish Rao, Kunal Talwar, STOC 2003 and JCSS 2004.
• Tree approximation for minimizing congestion
  • Minimizing Congestion in General Networks,
    Harald Racke, FOCS 2002.
  • Optimal Oblivious Routing in Polynomial Time,
    Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, and Harald Räcke, STOC 2003.
  • A polynomial-time tree decomposition to minimize congestion,
    Chris Harrelson, Kris Hildrum and Satish Rao, SPAA 2003.
• Local search
  • Local Search Heuristics for k-median and Facility Location Problems,
    Vijay Arya, Naveen Garg, Rohit Khandekar, Vinayaka Pandit, Adam Meyerson, and Kamesh Munagala, STOC 2001 and SICOMP 2004.
  • Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP,
    Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay V. Vazirani, JACM 2003.
• Orienteering and TSP with deadlines
  • Approximation Algorithms for Orienteering and Discounted-Reward TSP,
    Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, and Maria Minkoff, FOCS 2003.
  • Approximation Algorithms for Deadline-TSP,
    Nikhil Bansal, Avrim Blum, Shuchi Chawla, and Adam Meyerson, STOC 2004.
  • A Recursive Greedy Algorithm for Walks in Directed Graphs,
    Chandra Chekuri and Martin Pal, FOCS 2005.
• Cost sharing and stochastic optimization
  • Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem,
    Anupam Gupta, Amit Kumar, Martin Pál and Tim Roughgarden, FOCS 2003.
  • Boosted Sampling: Approximation Algorithms for Stochastic Optimization,
    Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha, STOC 2004.
• Iterative rounding
  • A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem, Kamal Jain, FOCS 1998 and Combinatorica 2001.
• Zero-extension and metric labeling
  • An improved approximation algorithm for the 0-extension problem, Jittat Fakcheroenphol, Chris Harrelson, Satish Rao and Kunal Talwar, SODA 2003.
  • On earthmover distance, metric labeling, and 0-extension, Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani, to appear in STOC 2006.
• Integrality gaps for SDP relaxations
  • The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into L1, Subhash Khot and Nisheeth Vishnoi, FOCS 2005.
  • Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems, Nikhil Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi, to appear in STOC 2006.