UIUC Computer Science Department

CS 598: Special Topics: Approximation Algorithms Chandra Chekuri

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
• Lower-stretch spanning trees. M. Elkin, Y. Emek, D. Spielman, S-H. Teng. SIAM J. on Computing, 2008; preliminary version in STOC 2005.
• Improved Embedding of Graph Metrics into Random Trees. K. Dhamdhere, A. Gupta, H. Racke. SODA 2006.
  (Note that the original version of this paper contained a bug; see Anupam Gupta's page.)
• Nearly Tight Low Stretch Spanning Trees. I. Abraham, Y. Bartal, O. Neiman. FOCS 2008
• 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
• Buy-at-bulk network design. B. Awerbuch and Y. Azar. FOCS 1997.
• A Constant Factor Approximation for the Single Sink Edge Installation Problem. S. Guha, A. Meyerson, K. Munagala. SIAM J. on Computing, 2008; preliminary versions in FOCS 2000 and STOC 2001.
• Cost-Distance: Two metric network design. A. Meyerson, K. Munagala, S. Plotkin. SIAM J. on Computing, 2008; preliminary version in FOCS 2000.
• Approximation Algorithms for Non-uniform Buy-at-Bulk Network Design Problems. C. Chekuri, M. Hajiaghayi, G. Kortsarz. M. Salavatipour. FOCS 2006.
• Network Design with Degree Constraints
• Approximating Minimum Bounded Degree Spanning Tress to within One of Optimal. M. Singh and L. Lau. STOC 2007.
• Survivable Network Design with Degree or Order Constraints. L. Lau, S. Naor, M. Salavatipour, M. Singh.
• Additive Guarantees for Directed Degree Bounded Network Design N. Bansal, R. Khandekar, V. Nagarajan. STOC 2008.
• Additive Approximation for Bounded Degree Survivable Network Design. L. Lau and M. Singh. STOC 2008
• 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
• Fast approximation algorithms for fractional packing and covering problem. S. Plotkin, D. Shmoys, E. Tardos. Math. of Operations Research, 1995; preliminary version in FOCS 1991.
• Randomized Rounding Without Solving the Linear Program. N. Young. SODA 1995.
• Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems.. N. Garg and J. Konemann.
  SIAM J. on Computing, 2007; preliminary version in FOCS 1998.
• Multiplicative weights method: a meta-algorithm and its applications. S. Arora, E. Hazan, S. Kale.
• Submodular function maximization subject to constraints
• Maximizing a Monotone Submodular Function subject to a Matroid Constraint. G. Calinescu, C. Chekuri, M. Pal, J. Vondrak. Preliminary versions in IPCO 2007 and STOC 2008.
• Non-monotone submodular maximization under matroid and knapsack constraints. J. Lee, V. Mirrokni, V. Nagarajan, M. Sviridenko. To appear in STOC 2009.
• Bandwidth via volume respecting embeddings
• Approximating the bandwidth via volume respecting embeddings. U. Feige. J. of Comp. and System Sciences, 2000.
• Flow Metrics. C. Bornstein and S. Vempala. Theoretical Comp. Science, 2004; preliminary version in LATIN 2002.
• Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. A. Blum, G. Konjevod, R. Ravi, S. Vempala. Theoretical Comp. Science, 2000; preliminary version in STOC 1998.
• Minimum Linear Arrangement
• New Approximation Techniques for Some Ordering Problems. S. Rao and A. W. Richa. SIAM J. on Computing, 2005; preliminary version in SODA 1998.
• Divide-and-conquer approximation algorithms via spreading metrics. G. Even, J. Naor, A. Rao, B. Schieber. J. of the ACM, 2000; preliminary version in FOCS 1995.
• l₂² spreading metrics for vertex ordering problems. M. Charikar, M. Hajiaghayi, H. Karloff, S. Rao. SODA 2006.
• Geometric Approximation
• Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems. Sanjeev Arora.
  J. of the ACM, 1998. Preliminary versions in FOCS 1996, FOCS 1997. Also see the survey by Arora that appeared in Math Programming.
• A Nearly Linear-time Approximation Scheme for the Euclidean k-median problem S. G. Kolliopolous and S. Rao. SIAM J. on Computing, 2007.
• PTASes for Planar Graphs and Extensions
• Approximation Algorithms for NP-Complete Problems on Planar Graphs. B. Baker. J. of the ACM, 1994.
• Diameter and treewidth in minor-closed graph families. D. Eppstein. Algorithmica, 2000.
• The Bidimensionality Theory and Its Algorithmic Applications. E. Demaine and M. Hajiaghayi. The Computer Journal, 2008.
• 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
• Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee. A. Ageev and M. Sviridenko.
  J. of Combinatorial Optimization 2004; preliminary version appeared as "Approximation algorithms for Maximum Coverage and Max Cut with given sizes of parts" in IPCO 1999.
• Dependent Rounding and its Applications to Approximation Algorithms. R. Gandhi, S. Khuller, S. Parthasarathy, A. Srinivasan. J. of the ACM, 2006.
• Metric Labeling and Related
• Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Partitioning and Markov Random Fields. J. Kleinberg and E. Tardos.
  J. of the ACM, 2002; preliminary version in FOCS 1999.
• Approximate classification via earthmover metrics. A. Archer, J. Fakcharoenphol, C. Harrelson, R. Krauthgamer, K. Talwar, E. Tardos. SODA 2004.
• Approximation Algorithms for the 0-Extension Problem. G. Calinescu, H. Karloff, Y. Rabani. SIAM J. on Computing, 2004; preliminary version in SODA 2001.