Course description:

The area of approximation algorithms deals with finding provable guarantees on the performance of heuristic solutions to hard combinatorial optimization problems. In this course, we will study some classical results and recent research directions in the area. See the topics covered in the prequel course Approximation Algorithms which I taught in Winter 2010. While that course is not a prerequisite, some familiarity with approximation algorithms will be expected. Each student will be expected to give a presentation on a topic chosen by the student. A list of topics and relevant papers is given below and suggestions are welcome.

Lectures:

• Introduction. Metric TSP and Eucledian TSP. See Survey by Arora. Survey.
• Iterative Rounding. See Notes (Chapter 4). Notes.
• Bin Packing. See Notes (L. C. Lau, R. Ravi and M. Singh). Notes.
• Online Primal-Dual Schema. See Survey by N. Buchbinder and S. Naor. Notes.

List of Topics and Relevant Papers:

• A constructive proof of the Lovasz Local Lemma, R. Moser, STOC 2009.
  • A constructive proof of the general Lovasz Local Lemma, Moser, Tardos, JACM 2010.
  • New Constructive Aspects of the Lovasz Local Lemma, Bernhard Haeupler, Barna Saha, Aravind Srinivasan, FOCS 2010.
• An O(k3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design Chuzhoy, Khanna, FOCS 2009.
  • An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem Lisa Fleischer, Kamal Jain, David P. Williamson, FOCS 2001.
  • Approximating minimum cost connectivity problems via uncrossable bifamilies Nutov, FOCS 2009.
• An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi, SODA 2010.
  • The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus Shayan Oveis Gharan, Amin Saberi, Preprint.
• An improved LP-based approximation for steiner tree J. Byrka, F. Grandoni, T. Rothvos, and L. Sanita. In ACM Symposium on Theory of Computing (STOC), 583-592, 2010.
  • Improved Steiner Tree Approximation in Graphs Gabriel Robins, Alexander Zelikovsky, SODA 2000.
• The Geometry of Scheduling Nikhil Bansal, Kirk Pruhs, FOCS 2010.
• Maximizing a submodular set function subject to a matroid constraintGruia Calinescu, Chandra Chekuri, Martin Pal and Jan Vondrak, STOC 2008+IPCO 2007.
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph SizeAnkur Moitra, FOCS 2009.
• Online Stochastic Matching: Beating 1-1/e Jon Feldman, Aranyak Mehta, Vahab Mirrokni, S. Muthukrishnan, FOCS 2009.
• One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk Ashish Goel, Ian Post, FOCS 2010.
• Optimal Hierarchical Decompositions for Congestion Minimization in Networks. Harald Raecke, STOC 2008.
• Differentially Private Combinatorial Optimization Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar, SODA 2010.