Approximation algorithms reading group

Meeting Time and Place

What to expect?

• We plan to read one paper on approximation algorithms each week
• There is a leader for every paper who will lead the discussion on the paper
• It is expected that every member of the reading group will read, at least lightly, the paper to be preseneted
• It is expected that every member of the reading group will lead the discussion on a paper
• A list of topics and specific papers is suggested below, but feel free to suggest your own (on approximation algorithms)

Next meetings

• Mohit Singh and Lap Chi Lau Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal, STOC 07

• A. Gupta, A. Kumar and T. Roughgarden Simpler and better approximation algorithms for network design STOC 2003

• K. Iwama, S. Miyuazaki and N. Yamauchi A 1.875-Approximation Algorithm for the Stable Marriage Problem SODA 2007

• S. Guha K. Munagala Model-driven Optimization using Adaptive Probes

• Irit Dinur The PCP Theorem by Gap Amplification

• Timothy M. Chan Polynomial-time approximation schemes for packing and piercing fat objects , J. Algorithms 03

• Jittat Fakcharoenphol, Satish Rao, Kunal Talwar A tight bound on approximating arbitrary metrics by tree metrics, STOC 03

• Gruia Calinescu, Howard Karloff, Yuval Rabani Approximation algorithms for the 0-extension problem, SODA 01

• Jyh-Han Lin Jeffrey Scott Vitter Approximation algorithms for geometric median problems, Information Processing Letters Volume 44 , Issue 5 (December 1992) Pages: 245 - 249

• K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP JACM 2003

• Noam Nisan and Amir Ronen. Algorithmic Mechanism Design, Games and Economic Behavior, STOC 99

• K. Jain and V. Vazirani. Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation, JACM 2001

• E. Chlamtac, K. Makarychev, and Y. Makarychev How to Play Unique Games Using Embeddings, FOCS 06

• M. Zinkevich. Online Convex Programming and Generalized Infinitesimal Gradient Ascent, ICML 2003

• Callahan and Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, JACM 1995
• Arya, Malamatos, Mount. Space-Efficient Approximate Voronoi Diagrams STOC 2002

• Marcin Bienkowski,Miroslaw Korzeniowski and Harald Räcke. A practical algorithm for constructing oblivious routing schemes, SPAA 2003

• Joseph S. B. Mitchell. A PTAS for TSP with Neighborhoods Among Fat Regions in the Plane, to appear in SODA 2007.

Previous meetings

• 8.6.2006: Some open problems
  
• 15.6.2006: Amit and I will present the paper:
  
• Arora, Rao and Vazirani, Expander flows, geometric embeddings and graph partitioning, STOC 2004.
• 22.6.2006: In continuation of the study of the applications of the ARV technique, I will present the paper:
  
• George Karakostas, A better approximation ratio for the Vertex Cover problem, ICALP 2005.

It will be nice if somebody can read and present the recent paper of Arora, Chlamtac, and Charikar from STOC 2006: New Approximation gaurantee for Chromatic Number
• 29.6.2006: Naveen presented the result of Michel Goemans on finding degree-bounded spanning treesi (FOCS 2006)
  
• 06.7.2006: Alantha will present the paper
  M. Charikar, K. Makarychev and Y. Makarychev, Near-Optimal Algorithms for Unique Games (STOC 2006).
• 06.14.2006: Anand will present the paper
  Lap Chi Lau, An Approximate Max-Steiner Tree-Packing Min-Steiner-Cut Theorem, (FOCS 2004).
• 06.20.2006: I will present the paper
  N. Bansal, A. Chakrabarti, A. Epstein and B. Schieber, A Quasi-PTAS for Unsplittable Flow on Line Graphs, (STOC 2006).