# Approximation algorithms and the hardness of approximation (11w5117)

Arriving in Banff, Alberta Sunday, November 27 and departing Friday December 2, 2011

## Organizers

Chandra Chekuri (University of Illinois, Urbana-Champaign)

Joseph Cheriyan (University of Waterloo)

Ryan O'Donnell (Carnegie Melon University)

Mohammad Salavatipour (University of Alberta)

David Williamson ( Cornell University)

## Objectives

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 highlight some of the new technical/mathematical directions in approximation guarantees (hierarchies of linear programming and semidefinite programming relaxations, uses of convex programming) and

hardness thresholds (boolean functions, noise stability). These directions will be the subject of either survey or focus talks.

(3) To examine some of the key problems in the area, even those beyond the reach of current techniques.

(3a) One specific topic on which we will focus is the status of the ``Unique Games Conjecture'', which states that unless P is equal to NP, there is no efficient algorithm to distinguish whether one can satisfy almost all constraints or almost no constraints of a particular type of

constraint satisfaction problem (Khot [K02]). It is not currently known whether Unique Games Conjecture is true. However, several quite exciting results have been shown by assuming the truth of the Unique Games Conjecture; in particular, matching hardness thresholds have been shown for several fundamental problems in combinatorial optimization, such as the maximum cut problem and the minimum vertex cover problem (Khot-Kindler-Mossel-O'Donnell [KKMO07], Khot-Regev [KR08]). There has been significant work on the Unique Games Conjecture both on the part of algorithms researchers and complexity theorists. The algorithms researchers are finding approximation algorithms for the Unique Games Problem; approximation algorithms with particular approximation guarantees will disprove the conjecture. The complexity theorists have

been using the Unique Games Conjecture to find additional hardness thresholds for fundamental problems. As part of the workshop, we will survey the current status of the conjecture, and devote time to approaches to resolve the conjecture, as well as further applications of it.

(3b) Another focus topic for the workshop is the hierarchy of LP (linear programming) and SDP (semidefinite programming) relaxations.

The key idea here is to start from an LP relaxation of an NP-hard problem, and then obtain a series of tighter and tighter LP or SDP relaxations, by adding auxiliary variables and linear or semidefinite constraints. These methods were developed by Balas [B85], Sherali and Adams [SA90], Lovasz and Schrijver [LS91], Lasserre [L01], etc., and capture most of the known LP and SDP relaxations that have been exploited in the design of approximation algorithms. A stream of exciting research starting from the work of Arora, Bollobas and Lovasz [ABL02], [ABLT06] has developed techniques to prove lower bounds on the approximation guarantees achievable by these methods. An important direction is to capture the relationship between hardness thresholds and the lower bound results on hierarchies of convex relaxations.

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

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

Although none of the organizers is female, we have informed several (at least five) of our female colleagues, and all are interested in

participating.

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) Raghavendra [R08] has recently shown that there is a fixed efficient semidefinite programming algorithm which achieves the best approximation guarantee for all constraint satisfaction problems -- assuming the Unique Games Conjecture.

(2) Asadpour, Goemans, Madry, Oveis Gharan, and Saberi [AGMOS09] very recently achieved the first significant improvement on the approximation guarantee of the asymmetric traveling salesman problem in over twenty five years.

The workshop will present an opportunity to bring together some of the experts in related fields with the hope of initiating collaboration on some of the major open problems, and to explore the wider ramifications of the evolving body of powerful results and techniques from our area.

REFERENCES

[ABL02] S.Arora, B.Bollobas, L.Lovasz: Proving Integrality Gaps without Knowing the Linear Program. FOCS 2002: 313-322

[ABLT06] S.Arora, B.Bollobas, L.Lovasz, I.Tourlakis: Proving Integrality Gaps without Knowing the Linear Program. Theory of Computing 2(1): 19-51 (2006)

[ALN07] S.Arora, J.R.Lee, A.Naor: Fre'chet Embeddings of Negative Type Metrics. Discrete & Computational Geometry 38(4): 726-739 (2007)

[ARV09] S.Arora, S.Rao, 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, A.Saberi, An O(log n/log log n) -Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Manuscript (2009)

[B85] E.Balas, Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM Journal on Algebraic and Discrete Methods 6:466--485 (1985)

[BC05] B.Brinkman, M.Charikar: On the impossibility of dimension reduction in $ell_1$. J. ACM 52(5): 766-788 (2005)

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

[GW95] M.X.Goemans, D.P.Williamson: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42(6): 1115-1145 (1995)

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

[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. STOC 2002: 767-775

[KKMO07] S.Khot, G.Kindler, E.Mossel, 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, O.Regev: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3): 335-349 (2008)

[LRS09] L.Lau, R.Ravi, M.Singh, Iterative methods in Combinatorial Optimization. Manuscript of monograph, 2009.

[L01] J.B.Lasserre: An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs. IPCO 2001: 293-303

[LLR95] N.Linial, E.London, 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)

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

[M08] E.Mossel: Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes. FOCS 2008: 156-165

[M09] E.Mossel: A Quantitative Arrow Theorem. arXiv:0903.2574v3 [math.PR] (2009)

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

[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, D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, to be published in 2010

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

(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 highlight some of the new technical/mathematical directions in approximation guarantees (hierarchies of linear programming and semidefinite programming relaxations, uses of convex programming) and

hardness thresholds (boolean functions, noise stability). These directions will be the subject of either survey or focus talks.

(3) To examine some of the key problems in the area, even those beyond the reach of current techniques.

(3a) One specific topic on which we will focus is the status of the ``Unique Games Conjecture'', which states that unless P is equal to NP, there is no efficient algorithm to distinguish whether one can satisfy almost all constraints or almost no constraints of a particular type of

constraint satisfaction problem (Khot [K02]). It is not currently known whether Unique Games Conjecture is true. However, several quite exciting results have been shown by assuming the truth of the Unique Games Conjecture; in particular, matching hardness thresholds have been shown for several fundamental problems in combinatorial optimization, such as the maximum cut problem and the minimum vertex cover problem (Khot-Kindler-Mossel-O'Donnell [KKMO07], Khot-Regev [KR08]). There has been significant work on the Unique Games Conjecture both on the part of algorithms researchers and complexity theorists. The algorithms researchers are finding approximation algorithms for the Unique Games Problem; approximation algorithms with particular approximation guarantees will disprove the conjecture. The complexity theorists have

been using the Unique Games Conjecture to find additional hardness thresholds for fundamental problems. As part of the workshop, we will survey the current status of the conjecture, and devote time to approaches to resolve the conjecture, as well as further applications of it.

(3b) Another focus topic for the workshop is the hierarchy of LP (linear programming) and SDP (semidefinite programming) relaxations.

The key idea here is to start from an LP relaxation of an NP-hard problem, and then obtain a series of tighter and tighter LP or SDP relaxations, by adding auxiliary variables and linear or semidefinite constraints. These methods were developed by Balas [B85], Sherali and Adams [SA90], Lovasz and Schrijver [LS91], Lasserre [L01], etc., and capture most of the known LP and SDP relaxations that have been exploited in the design of approximation algorithms. A stream of exciting research starting from the work of Arora, Bollobas and Lovasz [ABL02], [ABLT06] has developed techniques to prove lower bounds on the approximation guarantees achievable by these methods. An important direction is to capture the relationship between hardness thresholds and the lower bound results on hierarchies of convex relaxations.

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

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

Although none of the organizers is female, we have informed several (at least five) of our female colleagues, and all are interested in

participating.

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) Raghavendra [R08] has recently shown that there is a fixed efficient semidefinite programming algorithm which achieves the best approximation guarantee for all constraint satisfaction problems -- assuming the Unique Games Conjecture.

(2) Asadpour, Goemans, Madry, Oveis Gharan, and Saberi [AGMOS09] very recently achieved the first significant improvement on the approximation guarantee of the asymmetric traveling salesman problem in over twenty five years.

The workshop will present an opportunity to bring together some of the experts in related fields with the hope of initiating collaboration on some of the major open problems, and to explore the wider ramifications of the evolving body of powerful results and techniques from our area.

REFERENCES

[ABL02] S.Arora, B.Bollobas, L.Lovasz: Proving Integrality Gaps without Knowing the Linear Program. FOCS 2002: 313-322

[ABLT06] S.Arora, B.Bollobas, L.Lovasz, I.Tourlakis: Proving Integrality Gaps without Knowing the Linear Program. Theory of Computing 2(1): 19-51 (2006)

[ALN07] S.Arora, J.R.Lee, A.Naor: Fre'chet Embeddings of Negative Type Metrics. Discrete & Computational Geometry 38(4): 726-739 (2007)

[ARV09] S.Arora, S.Rao, 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, A.Saberi, An O(log n/log log n) -Approximation Algorithm for the Asymmetric Traveling Salesman Problem. Manuscript (2009)

[B85] E.Balas, Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM Journal on Algebraic and Discrete Methods 6:466--485 (1985)

[BC05] B.Brinkman, M.Charikar: On the impossibility of dimension reduction in $ell_1$. J. ACM 52(5): 766-788 (2005)

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

[GW95] M.X.Goemans, D.P.Williamson: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM 42(6): 1115-1145 (1995)

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

[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. STOC 2002: 767-775

[KKMO07] S.Khot, G.Kindler, E.Mossel, 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, O.Regev: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3): 335-349 (2008)

[LRS09] L.Lau, R.Ravi, M.Singh, Iterative methods in Combinatorial Optimization. Manuscript of monograph, 2009.

[L01] J.B.Lasserre: An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs. IPCO 2001: 293-303

[LLR95] N.Linial, E.London, 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)

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

[M08] E.Mossel: Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes. FOCS 2008: 156-165

[M09] E.Mossel: A Quantitative Arrow Theorem. arXiv:0903.2574v3 [math.PR] (2009)

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

[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, D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, to be published in 2010

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