E0 249: Approximation Algorithms, Spring 2015 -- Project List

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.