##
E0 249: Approximation Algorithms, Spring 2015.

**Instructors: Arnab Bhattacharyya and Deeparnab Chakrabarty **

** Methodology. ** In this reading project, you will have to read a paper and should be prepared to make a 30 minute presentation on it.
You can, and are encouraged to, do this in pairs. As a first step you should decide which paper you are going to read and let us know, and also tell who your partner is.
We give a list of papers below -- you are free to choose any of them, however, you can choose one of your own but then you must pass it by one of the instructors.

** Proposed Papers **
- Approximating ATSP by relaxing connectivity. Svennson, 2015. (
** Taken by Chinmay and Raghav. **)
- Approximating Graphic TSP by Matchings. Momke, Svensson, FOCS 2011.
**(Taken by Marilyn and Cressida)**
- Greedy algorithms for Steiner Forest. Gupta, Kumar, STOC 2015
** (Taken by Nithin and Jawad) **
- A Polylogarithmic Approximation for the Minimum Bisection Problem. Feige, Krauthgamer, FOCS 2000.
**(Taken by Abhijat and Saravanan)**
- The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme. Bartal, Gottlieb, Krauthgamer, STOC 2012.
- A Linear-time approximation scheme for TSP in Planar graphs with edge weights. Klein, FOCS 2005. (
** Taken by Anurita and Divya.**)
- The Directed Orienteering Porblem. Nagarajan, Ravi, Algorithmica 2011.
- Approximation Algorithms for Regret-Bounded Vehicle Routing
and Applications to Distance-Constrained Vehicle Routing.Friggstad, Swamy, STOC 2014.
- Steiner Tree Approximation via Iterative Randomized Rounding. Byrka, Grandoni, Rothvoss, Sanita, JACM 2013.
- A General Approximation Technique for Constrained Forest Problems. Goemans, Williamson, SODA 1992.
- Sparsest Cut on Bounded Treewidth Graphs., Gupta, Talwar, Witmer STOC 2013
- Online Submodular Maximization with Pre-emption Buchbinder, Feldman, Naor, 2015 (
** Taken by Amleshwar Kumar. **)
- The Santa Claus Problem Bansal, Sviridenko, STOC 2006 (
** Taken by Dheeraj Ram and Ajith S**)
- Excluded Minors, Network Decompositon, and Multicommodity Flow. Klein, Plotkin, Rao, 1993.
**(Taken by Indranil and Sayan.)**

Go back to course webpage.