CSE 522, Autumn 2009: Approximation Algorithms

Some open problems (This web page is under construction!)

Here are some important problems where there is a gap between the best approximation ratio we know how to achieve and the best hardness of approximation result we know, or else we just don't know much.

• TSP and ATSP. Here is the latest breakthrough paper on ATSP.
• Unique Games. For some basics on unique games, see Section 13.3 in Williamson and Shmoys.
• Congestion Minimization. Given a si, ti pairs, find paths from each si to ti that minimize the maximum congestion on any edge. Best upper bound is log n/loglog n (Raghavan and Thompson) and best hardness is loglog n (Andrews and Zhang)
• Disjoint Paths: Again, given undirected graph and collection of si, ti pairs,, find as many completely disjoint (edge-disjoint, or in a different version, vertex-disjoint) paths as possible. Best upper bound is sqrt(n), best hardness is polylog.
• Find a maximum weighted independent set among a set of axis-aligned rectangles in the plane. Best upper bound is log n (log log n for the unweighted case). At the moment, can't rule out a PTAS. (Interesting in more dimensions as well.)
• Firefighters problem. Best upper bound is sqrt(n), best hardness is constant.
• Combinatorial problems with submodular cost functions. A recent emerging direction is to consider your favorite hard combinatorial problem and replace the linear cost functions with a submodular cost function. See e.g. this hot-off-the-presses paper which contains some new results along these lines, lots of references and a bunch of open problems.

Here are some questions related to the techniques:

• Iterative Methods:
  • Can these ideas be used to make progress on TSP or ATSP? Some characterization results have been obtained by Goemans and Singh, but no one knows how to use them. For more details see Section 8.2 of Mohit Singh's Ph.D. thesis.
  • Goemans has an interesting conjecture about the single-source unsplittable min-cost flow problem, where again some partial progress follows from iterative techniques. See Skutella's paper and Section 8.2 of Mohit Singh's Ph.D. thesis. (The problem is that commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed a given budget.)
• Primal-dual methods
  • Survivable network design. Kamal Jain has a 2-approximation (Section 11.3 of Williamson and Shmoys). Lots of people think there should be a primal-dual algorithm for this problem, but the best primal-dual algorithm currently known only gets a log approximation.
  • Virtually all primal-dual approximation algorithms do dual ascent (i.e., dual variables never decrease). Can it help to allow for algorithms that do not change dual variables monotonically (as in exact primal-dual algorithms)? How can we approach this rigorously?
  • Is there a primal-dual algorithm for the Steiner Tree problem that beats a factor of 2? Potentially the bidirected relaxation could be helpful. (Google it.)
  • Develop a theory of primal-dual algorithms for maximization problems. There are very few results. Here is one example.

Here are some much more vague open-ended questions:

• Is there some technique more powerful than semidefinite programming?
• When do you actually have to solve an LP?
• Algorithm portfolios.
• Take some approximation algorithm analysis and extract from the analysis classes of inputs where it works really well, much better than the worst case assumption.
• Take your favorite hard problem that people out there actually care about, and for which there are algorithms that work well in practice (e.g. graph partitioning and clustering). Develop some theory to explain why these algorithms work well.

Thanks for Julia Chuzhoy and Tim Roughgarden for relevant discussions.