Approximation Algorithms and the Hardness of Approximation (14w5051)

Arriving Sunday, August 3 and departing Friday August 8, 2014


Chandra Chekuri (University of Illinois, Urbana-Champaign)
Joseph Cheriyan (University of Waterloo)
Ryan O'Donnell (Carnegie Mellon University)
Mohammad Salavatipour (University of Alberta)
David Williamson (Cornell University, School of Operations Research and Information Engineering)


The goals of the workshop are as follows:

(1) To bring together researchers in the fields of approximation algorithms (who work on finding algorithms with good approximation guarantees) and complexity theory (who work on finding hardness thresholds), and to stimulate the exchange of ideas and techniques between the two groups.

(2) To focus on a few key topics that could lead to deep new results in the areas of approximation algorithms, combinatorial optimization, hardness of approximation, and proof complexity. We describe a few ambitious topics below.

(2a) The most famous problem in all of discrete optimization is the Traveling Salesman Problem (TSP). Yet despite the attention paid to this problem, its approximability remains poorly understood. The best known approximation algorithm for the symmetric case is a 3/2-approximation algorithm due to Christofides from 1976. On the other hand, the known hardness-of-approximation results are weak, and there is a substantial gap between upper bounds and lower bounds.

Recently, there has been remarkable progress on some special cases of the TSP and on some variants of the TSP, but, as of now, there has been no improvement on the approximation guarantee of 3/2 for the TSP. Some of the recent advances were covered in the 2011 BIRS workshop, and a whole day was devoted to talks on the TSP and related problems. Many of these advances are based on new and beautiful connections with Probability Theory, coupled with technically difficult exploitation of methods and structures that are studied in Combinatorial Optimization. For example, Oveis Gharan, Saberi, and Singh [OSS11] used properties of strongly Rayleigh measures coupled with an elaborate analysis of the structure of near-minimum cuts to obtain the first improvement on the 3/2-approximation guarantee for a key special case called the graphic TSP; also, see Asadpour, et al. [AGMOS09]. The most recent result on this special case is a 7/5-approximation algorithm of Sebo and Vygen [SV12] that hinges on a probabilistic lemma of Momke and Svensson [MS11] coupled with an in-depth and novel analysis of structures that are well known in Combinatorial Optimization. An, Kleinberg, and Shmoys [AKS12] improved on a 20-year old 5/3-approximation guarantee of Hoogeveen [H91] for the s-t path TSP, which is a variant of TSP; they use a randomized rounding algorithm, and their improvement uses probabilistic methods coupled with an analysis of near-minimum cuts. Very recently, Sebo [S12] has improved on this result to obtain an 8/5-approxmation guarantee, by using further probabilistic insights.

It has long been conjectured that there is a 4/3-approximation algorithm for the TSP, and a 3/2-approximation algorithm for the s-t path TSP. By re-focusing attention on these conjectures, our goal is to continue the momentum from the 2011 BIRS workshop on the TSP.

(2b) Another focus topic will be approximation algorithms for disjoint paths and related routing problems. These problems are intimately related to fundamental topics on structural graph theory as well as to multicommodity flows. At the 2011 BIRS workshop, Chuzhoy [C12] presented a plenary talk on her breakthrough work that obtained the first poly-logarithmic approximation algorithm with constant congestion for the maximum edge-disjoint paths problem (MEDP). This built on a long line of work and numerous tools. There has been subsequent exciting progress including the work of Chuzhoy and Li [CL12] who improved the congestion bound from 14 to 2.

Despite this progress, the approximability of the maximum disjoint paths problem is wide open if the congestion bound is kept at one. Let $n$ denote the number of nodes of the input graph. The known upper bound is $O(\sqrt{n})$ while the lower bound is only sub-logarithmic in $n$ (namely, $\Omega(\log^{\frac{1}{2}-\epsilon}{n})$), see Andrews et al. [ACGKTZ10]. The approximability threshold is poorly understood even for restricted instances such as planar graphs and graphs of bounded treewidth. The impetus from the recent results and tools promises to lead to exciting new advances on algorithms for routing problems. The results of Chuzhoy [C12] have been extended to the maximum node-disjoint paths problem with constant congestion by Chekuri and Ene [CE13]. In addition, there are strong connections to structural aspects of graph theory. The recent progress on disjoint path problems is based on proving the existence of routing structures whose size is proportional to the treewidth of the graph, see [CE13]. This points to further connections between the above algorithmic results and the theory of Graph Minors developed by Robertson and Seymour, [RS83].

Our aim is to start systematic explorations of this connection. On the one hand, this could lead to the design of powerful new algorithmic tools for some of the routing problems that arise in many applied areas, and on the other hand, it could provide new techniques for attacking some of the significant conjectures within the theory of Graph Minors.

(2c) A key component of the workshop will focus on the notorious Unique Games Conjecture (UGC) and surrounding issues in the complexity of optimization problems. Since its proposal in 2002 by Khot [K02], the UGC has led to major new (conditional) inapproximability results for constraint satisfaction problems (CSPs). This culminated in Raghavendra's 2009 work [R09] giving a polynomial-time algorithm for optimally approximating each CSP, assuming the UGC.

The workshop will explore two directions that are at the vanguard of UGC research: improving optimization algorithms via Lasserre / SOS-proofs methodology, and going beyond the UGC in complexity results.

Lasserre / SOS algorithms.

In 2011, it was shown that the powerful Lasserre SDP hierarchy of algorithms (see [L01], and also see [SA90], [LS91]) could be used to obtain a subexponential-time algorithm for Unique Games (UG) (as in Arora et al. [ABS10]) and some related problems, see Barak et al. [BRS11] and Guruswami et al. [GS11]. (The 2011 BIRS workshop included two talks on these topics, by Georgiou and Steurer.) These results are motivating further advances in optimization using Lasserre algorithms.

A very recent, important work of Barak et al. [BBHKSZ12] emphasized and applied the connection between Lasserre algorithms and Sum-of-Squares (SOS) proof complexity; they showed that the known ``hard instances'' of the UG problem can be analyzed by constant-degree SOS proofs, and hence solved by a polynomial-time algorithm. Subsequent research furthered the connection to proof complexity, see O'Donnell et al. [OZ13]. The organizers are eager to bring together researchers working on optimization algorithms and on proof complexity, with the belief that these newly developed connections may lead to dramatic breakthroughs in efficient approximation algorithms.

Beyond the UGC.

One emerging stream of current research is concerned with going beyond the UGC. In one direction, going beyond the UGC has involved ``upgrading'' known UG-hardness results to full-fledged NP-hardness results. New techniques in this area, such as ``smooth Label Cover'' (see Guruswami et al. [GRSW12] and Hastad [H12]) and ``PCPs robust gainst low-degree polynomials'' (see Chan [Chan12] and Khot et al. [KST12]), are giving hope that many optimization tasks known to be ``UG-hard'' can be proved to be NP-hard without needing to resolve the UGC.

In the other direction, going beyond the UGC involves introducing alternative conjectures which can lead to inapproximability results not provable via UGC; one example is the Projection Games Conjecture introduced at the 2011 BIRS workshop by Moshkovitz [M12].

(3) To include many younger researchers, and foster a relaxed interaction with established researchers. At present, we have informed only a small number of young researchers. If the workshop is approved, then we will invite other young researchers. Our goal is to have a third of the workshop participants from this group. We expect a good number of female participants, similar to the workshop 11w5117.

(4) To allow groups of Canadian researchers working in this area to meet, and either initiate or renew collaborations.

Timeliness and appropriateness of the workshop

The study of approximation algorithms and the hardness of approximation is one of the most exciting areas among researchers in theoretical computer science; every major conference in the field has several papers on these topics. Significant progress is being made. We give two examples of recent, dramatic innovations:

(1) Arora, Barak and Steurer [ABS10] recently presented a sub-exponential-time algorithm for Unique Games. This is a landmark result on one of the most perplexing questions in the area, namely the Unique Games Conjecture (UGC). While this result does not disprove the UGC, it gives strong indications that the UGC may not be true. The implication is that some of the remarkable tight approximation thresholds proved assuming the UGC need to be revisited; one possibility is that substantially deeper methods may be needed to prove the tightness of these approximation thresholds assuming the P.not.=NP conjecture.

(2) Chuzhoy and Li [CL12] (FOCS 2012) very recently presented an approximation algorithm for maximizing the numer of edge disjoint paths with congestion two that acieves a poly-logarithmic approximation guarantee with respect to a standard LP relaxation. This is a remarkable achievement, because their LP relaxation has an integrality ratio that is much higher (than poly-logarithmic) for congestion one, meaning that poly-logarithmic approximation guarantees for congestion one are not possible (based on their LP relaxation); moreover, qualitatively speaking, the approximation guarantee for congestion two is best possible, due to lower bounds from the area of hardness of approximation.


[AKS12] H.-C.An, R.Kleinberg, and D.B.Shmoys: Improving Christofides' algorithm for the s-t path TSP. ACM STOC: 875-886 (2012)

[ACGKTZ10] M.Andrews, J.Chuzhoy, V.Guruswami, S.Khanna, K.Talwar, and L.Zhang: Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs. Combinatorica 30(5): 485-520 (2010)

[ABS10] S.Arora, B.Barak, and D.Steurer: Subexponential algorithms for Unique Games and related problems. IEEE FOCS: 563-572 (2010)

[ALN07] S.Arora, J.R.Lee, and A.Naor: Fre'chet embeddings of negative type metrics. Discrete & Computational Geometry 38(4): 726-739 (2007)

[ARV09] S.Arora, S.Rao, and U.V.Vazirani: Expander flows, geometric embeddings and graph partitioning. J.ACM: 56(2) (2009)

[AGMOS09] A.Asadpour, M.Goemans, A.Madry, S.Oveis Gharan, and A.Saberi: An O(log n/log log n)-approximation algorithm for the asymmetric Traveling Salesman Problem. ACM-SIAM SODA: 379-389 (2010)

[BRS11] B.Barak, P.Raghavendra, and D.Steurer: Rounding semidefinite programming hierarchies via global correlation. IEEE FOCS: 472-481 (2011)

[BBHKSZ12] B.Barak, F.Brandao, A.Harrow, J.Kelner, D.Steurer, and Y.Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. ACM STOC: 307-326 (2012)

[Chan12] Siu On Chan. Approximation resistance from pairwise independent subgroups. Technical Report TR12-110, ECCC (2012)

[CE13] C.Chekuri, and A.Ene: Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. To appear in ACM-SIAM SODA (2013)

[C12] J.Chuzhoy: Routing in undirected graphs with constant congestion. STOC: 855-874 (2012)

[CL12] J.Chuzhoy, and S.Li: A polylogarithimic approximation algorithm for Edge-Disjoint Paths with congestion 2. CoRR abs/1208.1272 (2012) To appear in IEEE FOCS (2012)

[F98] U.Feige: A threshold of $\ln{n}$ for approximating Set Cover. J. ACM 45(4): 634-652 (1998)

[GW95] M.X.Goemans, and D.P.Williamson: Improved approximation algorithms for Maximum Cut and Satisfiability problems using semidefinite programming. J. ACM 42(6): 1115-1145 (1995)

[GS11] V.Guruswami, A.K.Sinop: Lasserre hierarchy, higher eigenvalues, and approximation schemes for quadratic integer programming with PSD objectives. IEEE FOCS: 482-491 (2011)

[GRSW12] V.Guruswami, P.Raghavendra, R.Saket, and Y.Wu: Bypassing UGC from some optimal geometric inapproximability results. ACM-SIAM SODA: 699-717 (2012)

[H01] J.Hastad: Some optimal inapproximability results. J.ACM 48(4): 798-859 (2001)

[H12] J.Hastad: On the NP-hardness of Max-Not-2. Approx-Random: 170-181 (2012)

[H91] J.A.Hoogeveen: Analysis of Christofides' heuristic: Some paths are more difficult than cycles. Operations Research Letters 10: 291-295 (1991)

[J01] K.Jain: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1): 39-60 (2001)

[K02] S.Khot: On the power of unique 2-prover 1-round games. ACM STOC: 767-775 (2002)

[KKMO07] S.Khot, G.Kindler, E.Mossel, and R.O'Donnell: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37(1): 319-357 (2007)

[KR08] S.Khot, and O.Regev: Vertex cover might be hard to approximate to within $2-\epsilon$. J. Comput. Syst. Sci. 74(3): 335-349 (2008)

[KST12] S.Khot, M.Safra, and M.Tulsiani. Towards an optimal query efficient PCP? Technical Report TR12-109, ECCC (2012)

[L01] J.B.Lasserre: An explicit exact SDP relaxation for nonlinear 0-1 programs. IPCO (Integer Programming and Combinatorial Optimization): 293-303 (2001)

[LRS11] L.Lau, R.Ravi, and M.Singh, Iterative Methods in Combinatorial Optimization. Cambridge University Press, Cambridge, U.K., 2011.

[LLR95] N.Linial, E.London, and Y.Rabinovich: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2): 215-245 (1995)

[LS91] L.Lovasz, and A.Schrijver: Cones of matrices and set functions, and 0-1 optimization. SIAM Journal on Optimization 1: 166--190 (1991)

[MS11] T.Momke, and O.Svensson: Approximating graphic TSP by matchings. IEEE FOCS: 560-569 (2011)

[M12] D.Moshkovitz: The Projection Games Conjecture and the NP-hardness of $\ln{n}$-approximating Set-Cover. Approx-Random: 276-287, 2012.

[MOO05] E.Mossel, R.O'Donnell, and K.Oleszkiewicz: Noise stability of functions with low influences: invariance and optimality. IEEE FOCS: 21-30 (2005)

[OZ13] R.O'Donnell, and Y.Zhou: Approximability and proof complexity. To appear in ACM-SIAM SODA 2013.

[OSS11] S.Oveis Gharan, A.Saberi, and M.Singh: A randomized rounding approach to the Traveling Salesman Problem. IEEE FOCS: 550-559 (2011)

[R08] P.Raghavendra: Optimal algorithms and inapproximability results for every CSP? ACM STOC: 245-254 (2008)

[R09] P.Raghavendra: Approximating NP-hard problems: efficient algorithms and their limits. Ph.D. thesis, University of Washington, 2009.

[RS83] N.Robertson, and P.D.Seymour, Graph Minors I. J.Comb. Theory, Ser.B 35(1): 39-61 (1983), to Graph Minors XXIII. J.Comb. Theory, Ser.B 100(2): 181-205 (2010)

[S12] A.Sebo: Eight fifth approximation for TSP paths. Manuscript, 2012.

[SV12] A.Sebo, and J.Vygen: Shorter tours by nicer ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. CoRR, abs/1201.1870v2 (2012)

[SA90] H.D.Sherali, and W.P.Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3 (3):411--430 (1990)

[V01] V.V.Vazirani, Approximation Algorithms. Springer-Verlag, Berlin, (2001)

[WS10] D.P. Williamson, and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, Cambridge, U.K., 2011.

[Z07] D.Zuckerman, Linear degree extractors and the inapproximability of Max Clique and Chromatic Number, Theory of Computing 3(6): 103-128 (2007)