

Spring 2009

Course Projects
Instead of the last 3 homeworks, you can
choose to do a course project. The project can involve research on a
particular problem or topic in approximation algorithms, a survey of
several papers on a topic, an application or implementation of
approximation algorithms to a problem in your research area,
etc. Other project ideas are also acceptable; please talk to us about
any such ideas you have.
A list (that will be updated) of potential project topics and relevant
papers is given below. If you would like to work on a specific topic
not on this list, please discuss it with us over the next week.
You can work on the project in a group with one other person (that is,
in groups of size 2). Each group must prepare a 6page report and a
~25 minute presentation summarizing their project; these are due at
the end of the semester.
Project Topic List:
 Spanning tree embeddings
 Disjoint Paths and Routing
 An
O(\sqrt{n}) Approximation and Integrality Gap for Disjoint Paths and UFP.
C. Chekuri, S. Khanna, B. Shepherd. Theory of Computing, 2006.
 Multicommodity flow,
welllinked terminals, and routing problems. C. Chekuri, S. Khanna, B. Shepherd.
STOC 2005.
 The AllorNothing
Multicommodity Flow Problem.
C. Chekuri, S. Khanna, B. Shepherd. STOC, 2004. (See comment on
Chandra's page regarding congestion 1.)
 EdgeDisjoint
Paths in Planar Graphs with Constant Congestion. C. Chekuri, S. Khanna, B. Shepherd.
To appear in SICOMP special issue for STOC, 2006.
 Orienteering
 Approximation Algorithms
for Orienteering and DiscountedReward TSP.
A. Blum, S. Chawla, D. Karger, A. Meyerson, M. Minkoff, T. Lane.
SIAM J. on Computing, 2007; preliminary version in FOCS 2003.
 Approximation Algorithms
for DeadlineTSP and Vehicle Routing with TimeWindows.
N. Bansal, A. Blum, S. Chawla, A. Meyerson. STOC 2004.

Polylogarithmic Approximation Algorithms for Directed Vehicle Routing Problems.
V. Nagarajan and R. Ravi. APPROX 2007.
 Improved Algorithms
for Orienteering and Related Problems.
C. Chekuri, N. Korula, M. Pal. SODA 2008.
 BuyatBulk Network Design
 Network Design with Degree Constraints
 Feedback Problems
 An 8Approximation
Algorithm for the Subset Feedback Vertex Set Problem. G. Even, J. Naor, L. Zosin.
SIAM J. on Computing, 2000; preliminary version in FOCS 1996.
 Approximating Minimum
Subset Feedback Sets in Undirected Graphs with Applications to Multicuts.
G. Even, J. Naor, B. Schieber, L. Zosin.
SIAM J. Discrete Math., 2000;
preliminary version in Israel Symposium on Theory of Computing and Systems, 1996.
 Chapter 6 in the course textbook, Approximation Algorithms. Vijay Vazirani. SpringerVerlag, 2001.
 Solving Packing and Covering LPs Approximately
 Submodular function maximization subject to constraints
 Bandwidth via volume respecting embeddings
 Minimum Linear Arrangement
 Geometric Approximation
 PTASes for Planar Graphs and Extensions
 Group Steiner tree and Directed Steiner trees
 A polylogarithmic approximation
algorithm for the group Steiner problem.
N. Garg, G. Konjevod, R. Ravi. J. of Algorithms, 2000; preliminary version in SODA 1998.
 Approximation algorithms for the
covering Steiner problem.
G. Konjevod, R. Ravi, A. Srinivasan. Random Structures and Algorithms, 2002.
 Approximation Algorithms
for Directed Steiner Problems. M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, M. Li.
J. of Algorithms, 1999; preliminary version in SODA 1998.
 A Recursive Greedy
Algorithm for Walks in Directed Graphs. C. Chekuri and M. Pal. FOCS 2005.
 Dependent Randomized Rounding and Applications
 Metric Labeling and Related