|
|
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 6-page 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,
well-linked terminals, and routing problems. C. Chekuri, S. Khanna, B. Shepherd.
STOC 2005.
- The All-or-Nothing
Multicommodity Flow Problem.
C. Chekuri, S. Khanna, B. Shepherd. STOC, 2004. (See comment on
Chandra's page regarding congestion 1.)
- Edge-Disjoint
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 Discounted-Reward 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 Deadline-TSP and Vehicle Routing with Time-Windows.
N. Bansal, A. Blum, S. Chawla, A. Meyerson. STOC 2004.
-
Poly-logarithmic 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.
- Buy-at-Bulk Network Design
- Network Design with Degree Constraints
- Feedback Problems
- An 8-Approximation
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. Springer-Verlag, 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