Approximation Algorithms and the Hardness of Approximation (17w5133)

Arriving in Banff, Alberta Sunday, November 12 and departing Friday November 17, 2017


(Toyota Technological Institute at Chicago)

(University of Alberta)

Jochen Koenemann (University of Waterloo)

(Cornell University)

(École Polytechnique Fédérale de Lausanne)


(1) To bring together leading researchers in the fields of approximation algorithms and complexity theory, 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 topics below.

(2a) The most famous problem in all of discrete optimization is perhaps 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 classic 3/2-approximation algorithm due to Christofides from 1976. On the other hand, the known hardness-of-approximation results are very weak.

Over the last few years, there has been remarkable progress on several special cases of the TSP and on some closely related problems. Many of these advances are introducing new and very interesting connections between different areas such as probability, structural graph theory, coupled with technically difficult yet powerful new methods such as interlacing families of polynomials. In 2011 Oveis Gharan et al. [OSS11] used properties of strongly Rayleigh measures together 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 of TSP called the graphic TSP. Since then, there has been a series of more work on this special case and related questions. The most recent result on this special case is a 7/5-approximation algorithm of Sebo and Vygen [SV12] that hinges on a key 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 et al. [AKS12] improved on a 20-year old 5/3-approximation guarantee of Hoogeveen [H91] for the s-t path TSP. More recently, Sebo [S13] and Vygen [V15] have improved on these results to obtain an 1.599-approximation guarantee, by using further probabilistic insights. Relying on (and extending) the major result by Marcus, Spielman, and Srivastava [MSS15] that proves a conjecture of Kadison-Singer, Anari and Oveis Gharan [AO15] recently showed the existence of O(polyloglog n)-thin spanning trees. The result implies an O(polyloglog n) upper bound on the integrality gap of the Held-Karp LP relaxation for the asymmetric TSP (improving the O(log n/loglog n) bound from 2010 [AGMOS10]). The LP is long conjectured to have an O(1) integrality gap. The result of [AO15], however, does not imply an approximation algorithm, it only provides an estimate of the optimum value. Almost concurrently, Svensson [S15] showed that for the case of shortest path metrics of directed graphs (graphic ATSP), the integrality gap of the Held-Karp LP is O(1) and provides an efficient algorithm for it. The two biggest open problems in this area remain to improve upon the 3/2-approximation for TSP and to obtain a constant factor approximation for ATSP. By re-focusing attention on this problem, our goal is to continue the momentum from the past two workshops.

(2b) The Unique Games Conjecture (UGC) which was posed in 2002 by Khot [K02] and the implications of it have attracted a lot of attention over the last 13 years. The conjecture states that a certain type of constraint satisfaction problem is hard to approximate. If the conjecture is true, it shows that many of the approximation algorithms we have (in particular SDP based algorithms) are best possible ([R08, KR08, KKMO7]). More specifically UGC implies near tight approximatibility thresholds for a large class of constraint satisfaction problems (CSPs) among others (see Raghavendra [R09]). In a sense, UGC predicts that there is a "meta-algorithm" that is optimal for those problems and this meta-algorithm is based on SDP [BS14]. Refuting the conjecture would most likely require designing new algorithmic techniques that could potentially lead to improved approximation algorithms for many other problems. One component of the workshop will focus on this conjecture and surrounding issues in the complexity of optimization problems.

Lasserre hierarchy / Sum-of-Squares algorithms:

Use of semidefinite programming (SDP) relaxations and the lift-and-project strengthening of them has attracted a lot of attention in the field in the last decade or so. The Lasserre hierarchy is a systematic method of strengthening SDP relaxations by adding more constraints. In some instances these methods have been successfully applied to obtain improved approximation algorithms for some classical results (e.g. [C07]). More importantly, although some results support the UGC, some recent works have cast more doubts on it using Lasserre SDP based algorithms. For example, Arora et al. [ABS10] shown that the powerful Lasserre SDP hierarchy of algorithms could be used to obtain a subexponential-time algorithm for Unique Games (UG). More recently, Barak et al. [BBHKSZ12] have used used the connection between Lasserre algorithms and Sum-of-Squares (SOS) proof complexity, and have shown that the known hard instances of the UG problem can be analyzed by constant-degree SOS proofs, and thus be solved efficiently.

Extended formulations and their complexity

Feasible solutions to instances of combinatorial optimization problems often naturally correspond to the vertices of certain polyhedra. One way of designing an efficient algorithm for a given optimization problem is therefore to find a compact description for the associated polyhedron, and to then apply an efficient LP algorithm. In ground-breaking work Yannakakis [Ya91] first showed that for the TSP, every symmetric LP formulation must have an exponential number of constraints. Symmetry here means that for every permutation of cities there is a corresponding permutation of the variables that leaves the LP invariant. Fiorini et al. [FM+12] recently resolved Yannakakis' main open problem and showed that TSP has no symmetric or asymmetric polynomial-sized formulation. In another breakthrough, Rothvoss [R14] recently showed that no subexponential-size extended formulation can exist for the matching polyhedron either.

(2c) Routing problems in graphs arise in many areas of computers science, from VLSI design to Robotics. They have also been extensively studied in the graph theory community. Two of the most basic graph routing problems are the Edge Disjoint Paths (EDP) problem and Congestion Minimization. In EDP, we have to route a maximum number of demand pairs from a given collection in a graph via disjoint paths. In Congestion Minimization, all demand pairs must be routed, while minimizing the maximum load on any edge. Both problems are still poorly understood: for EDP the best upper and lower bounds have ratios $O(n^{1/2})$ [KS04] and $\Omega(\log^{1/2}n)$ [AZ05,ACG+10], while the upper and lower bounds for congestion minimization have ratios $O(\log n/\log\log n)$ [RT87] and (roughly) $\Omega(\log\log n)$ [AZ07], respectively. If one allows up to 2 paths to share an edge, a polylogarithmic approximation was recently shown [Chu12, CL12]. Graph routing problems are naturally closely related to network cuts and flows. The new techniques for graph decomposition introduced in [Chu12] have lead to new results in several other areas, such as a polynomial bound for the Excluded Grid Theorem of Robertson and Seymour [CC14]. Another closely related topic is graph sparsification: given a graph G and a small subset T of its vertices, called terminals, we would like to "compress" G into a much smaller graph H that contains the vertices of T, so that H behaves similarly to G with respect to the terminals. Graph sparsifiers naturally arise in approximation algorithms, graph theory, and fixed parameter tractability, and they have been studied in all these communities, often independently. If we require that the sparsifier H only contains the terminals, then there are known constructions that achieve quality (approximation factor) $O(\log k/\log\log k)$ for both the cut and the flow sparsifiers [Moi09, LM10, CLLM10, MM10, EGK+10], and it is known that no better than $\Omega(\sqrt{\log n})$-quality is achievable for this setting [FJS88, MM10,CLLM10,EGK10]. If H is allowed to contain additional vertices, better results (namely constant-quality) are known. Unfortunately, we still do not know whether it is possible to construct constant-quality cut and flow sparsifiers whose size only depends on k. Some of these recent results rely on graph decomposition techniques that were developed in the area of approximation algorithms for graph routing problems. Quality-1 cut sparsifiers were introduced under the name of mimicking networks by Hagerup et al. [HNKR98], and they have been used to provide kernels for various cut problems, such as, for example, minimum multiway cut [KW12]. However, the best current upper and lower bounds on the size of a mimicking network are $2^{2^{O(k)}}$ [HNKR98,KRTV12,CE10] and $2^{\Omega(k)}$ [KR12,KRTV12], respectively, which show that even this very basic problem is still not well understood.

(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.

(4) To allow groups of Canadian researchers working in this area to meet, and either initiate or renew collaborations. 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.

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. There are some very interesting progresses made on the topics mentioned above. Here are a few examples:

(1) The body of work around TSP in the last 5 years has been very exciting with several new developments. The more recent results of Anari and Oveis Gharan [AO15] and Svensson [S15] are two major breakthrough results on the ATSP using two completely different approaches.

(2) Arora, Barak and Steurer [ABS10] 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. More recently Barak et al [BBHKSZ12] show that all hard instances for UGC and SSEH can be solved by SOS algorithms. As a result we do not know of any examples that can be good candidate for "hard instances" for UGC and SSEH.




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

[AO15] A. Anari and S. Oveis Gharan: Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. IEEE FOCS 2015.

[ACG+10] 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).

[AZ05] M. Andrews and L. Zhang: Hardness of the undirected edge-disjoint paths problem. ACM STOC: 276-283 (2005).

[AZ07] M. Andrews and L. Zhang: Hardness of the undirected congestion minimization problem. SIAM J. Comput., 37(1):112-131 (2007).

[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)

[AGMOS10] 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)

[BS14] B.Barak and D.Steurer, Sum-of-squares proofs and the quest toward optimal algorithms . In Proceedings of International Congress of Mathematicians (ICM), 2014.

[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)

[CE10] E. W. Chambers and D. Eppstein: Flows in one-crossing-minor-free graphs. ISAAC (1), volume 6506 LNCS, pages 241-252 (2010).

[CLLM10] M. Charikar, T. Leighton, S. Li, and A. Moitra: Vertex sparsifiers and abstract rounding algorithms. IEEE FOCS, 265-274 (2010).

[CC14] C. Chekuri and J. Chuzhoy: Polynomial bounds for the grid-minor theorem. ACM STOC (2014).

[C07] E.Chlamtac, Approximation algorithms using hierarchies of semidefinite programming relaxations, in Proc. IEEE FOCS:691-701 (2007)

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

[CL12] J. Chuzhoy and S. Li: A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. IEEE FOCS (2012).

[EGK+10] M. Englert, A. Gupta, R. Krauthgamer, H. Raecke, I. Talgam-Cohen, and K. Talwar: Vertex sparsifiers: new results from old techniques. APPROX/RANDOM, pages 152--165 (2010).

[F98] U.Feige: A Threshold of ln n for Approximating Set Cover. J. ACM 45(4): 634-652 (1998)

[FJS88] T. Figiel, W. B. Johnson, and F. Schechtman: Factorizations of natural embeddings of $l^n\_p$ into L\_r. I. Studia Math., 89:79--103 (1988).

[FM+12] S. Fiorini, S. Massar, S. Pokutta, H. Tiwary, and R. deWolf. Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In STOC, pages 95-106, 2012.

[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)

[HNKR98] T. Hagerup, N. Nishimura, J. Katajainen, and P. Ragde: Characterizing multiterminal flow networks and computing flows in networks of bounded treewidth. J. Comput. Syst. Sci., 57 (1998).

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

[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)

[KRTV12] A. Khan, P. Raghavendra, P. Tetali, and L. A. Vegh. On mimicking networks representing minimum terminal cuts. CoRR, abs/1207.6371, (2012).

[K02] S.Khot: On the power of unique 2-prover 1-round games. 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)

[KS04] S. G. Kolliopoulos and C. Stein: Approximating disjoint-path problems using packing integer programs. Mathematical Programming, 99:63--87, (2004).

[KW12] S. Kratsch and M. Wahlstrom: Representative sets and irrelevant vertices: New tools for kernelization. IEEE FOCS (2012).

[KR12] R. Krauthgamer and I. Rika: Mimicking networks and succinct representations of terminal cuts. CoRR, abs/1207.6246, (2012).

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

[LM10] F. T. Leighton and A. Moitra: Extensions and limits to vertex sparsification. ACM STOC: 47-56 (2010).

[MM10] K. Makarychev and Y. Makarychev: Metric extension operators, vertex sparsifiers and Lipschitz extendability. IEEE FOCS 255-264 (2010).

[MSS15] A. W. Marcus, D. A. Spielman, and N. Srivastava, Interlacing families II: mixed characteristic polynomials and the Kadison-Singer problem, Ann. of Math. 182-1 (2015), 327-350.

[Moi09] A. Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. IEEE FOCS, 2-12 (2009).

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

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

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

[RT87] P. Raghavan and C. D. Tompson: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7:365-374, (1987).

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

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

[R14] T. Rothvoss: The matching polytope has exponential extension complexity. STOC: 263-272 (2014)

[S13] A.Sebo: Eight fifth approximation for TSP paths. IPCO 2013: 362-374 (2013).

[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)

[S15] O. Svensson, Approximating ATSP by Relaxing Connectivity. IEEE FOCS 2015.

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

[V15] J.Vygen: Reassembling trees for the traveling salesman. CoRR, abs/1502.03715.

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

[Ya91] Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences, 43(3):441-466, 1991.

[Z07] D.Zuckerman, Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number, Theory of Computing Volume 3 Article 6: 103-128 (2007)