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.