An optimal sdp algorithm for max-cut, and equally optimal long code tests

ABSTRACT

Let G be an undirected graph for which the standard Max-Cut SDP relaxation achieves at least a c fraction of the total edge weight, 1/2 <= c <= 1. If the actual optimal cut for G is at most an s fraction of the total edge weight, we say that (c, s) is an SDP gap. We define the SDP gap curve GapSDP : [1/2,1] -> [1/2,1] by GapSDP(c) = inf{s : (c, s) is an SDP gap}. In this paper we complete a long line of work [15, 14, 20, 36, 19, 17, 13, 28] by determining the entire SDP gap curve; we show GapSDP(c) = S(c) for a certain explicit (but complicated to state) function S. In particular, our lower bound GapSDP(c) - S(c) is proved via a polynomial-time - RPR²' algorithm. Thus we have given an efficient, optimal SDP-rounding algorithm for Max-Cut. The fact that it is RPR² confirms a conjecture of Feige and Langberg [17]. We also describe and analyze the tight connection between SDP gaps and Long Code tests (and the constructions of [25, 3, 4]). Using this connection, we give optimal Long Code tests for Max-Cut. Combining these with results implicit in [27, 29] and ideas from [19], we derive the following conclusions: - The Max-Cut SDP gap curve subject to triangle inequalities is also given by S(c). - No RPR² algorithm can be guaranteed to find cuts of value larger than S(c) in graphs where the optimal cut is c. (Contrast this with the fact that in the graphs exhibiting the c vs. S(c) SDP gap, our RPR² algorithm actually finds the optimal cut.) - Further, no polynomial-time algorithm of any kind can have such a guarantee, assuming P ≠ NP and the Unique Games Conjecture.

REFERENCES

• 1: N. Alon, K. Makarychev, Y. Makarychev, and A. Naor. Quadratic forms on graphs. Invent. Math., 163(3):499--522, 2006.
• 2: Noga Alon , Assaf Naor, Approximating the Cut-Norm via Grothendieck's Inequality, SIAM Journal on Computing, v.35 n.4, p.787-803, 2006 [doi>10.1137/S0097539704441629]
• 3: Noga Alon , Benny Sudakov, Bipartite Subgraphs and the Smallest Eigenvalue, Combinatorics, Probability and Computing, v.9 n.1, p.1-12, January 2000 [doi>10.1017/S0963548399004071]
• 4: Noga Alon , Benny Sudakov , Uri Zwick, Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms, SIAM Journal on Discrete Mathematics, v.15 n.1, p.58-72, 2002 [doi>10.1137/S0895480100379713]
• 5: Sanjeev Arora , Eli Berger , Elad Hazan , Guy Kindler , Muli Safra, On Non-Approximability for Quadratic Programs, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.206-215, October 23-25, 2005 [doi>10.1109/SFCS.2005.57]
• 6: Per Austrin, Balanced max 2-sat might not be the hardest, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250818]
• 7: Per Austrin, Towards Sharp Inapproximability For Any 2-CSP, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.307-317, October 21-23, 2007 [doi>10.1109/FOCS.2007.73]
• 8: A. Avidor and U. Zwick. Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT. In Proc. 8th APPROX, pages 14--25, 2005.
• 9: Nikhil Bansal , Avrim Blum , Shuchi Chawla, Correlation Clustering, Machine Learning, v.56 n.1-3, p.89-113 [doi>10.1023/B:MACH.0000033116.57574.95]
• 10: Francisco Barahona , Martin Grötschel , Michael Jünger , Gerhard Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design, Operations Research, v.36 n.3, p.493-513, May/June 1988 [doi>10.1287/opre.36.3.493]
• 11: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 12: C. Borell. Geometric bounds on the Ornstein-Uhlenbeck velocity process. Z. Wahrsch. Verw. Gebiete, 70(1):1--13, 1985.
• 13: Moses Charikar , Anthony Wirth, Maximizing Quadratic Programs: Extending Grothendieck's Inequality, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.54-60, October 17-19, 2004 [doi>10.1109/FOCS.2004.39]
• 14: Charles Delorme , Svatopluk Poljak, Combinatorial properties and complexity of a max-cut approximation, European Journal of Combinatorics, v.14 n.4, p.313-333, July 1993 [doi>10.1006/eujc.1993.1035]
• 15: C. Delorme , S. Poljak, Laplacian eigenvalues and the maximum cut problem, Mathematical Programming: Series A and B, v.62 n.3, p.557-574, Dec. 8, 1993 [doi>10.1007/BF01585184]
• 16: Uriel Feige , Marek Karpinski , Michael Langberg, Improved approximation of max-cut on graphs of bounded degree, Journal of Algorithms, v.43 n.2, p.201-219, May 2002 [doi>10.1016/S0196-6774(02)00005-6]
• 17: Uriel Feige , Michael Langberg, The RPR² rounding technique for semidefinite programs, Journal of Algorithms, v.60 n.1, p.1-23, July 2006 [doi>10.1016/j.jalgor.2004.11.003]
• 18: Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
• 19: Uriel Feige , Gideon Schechtman, On the optimality of the random hyperplane rounding technique for max cut, Random Structures & Algorithms, v.20 n.3, p.403-440, May 2002 [doi>10.1002/rsa.10036]
• 20: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 21: A. Grothendieck. Resume de la theorie metrique des produits tensoriels topologiques. Bol. Soc. Mat. Sao Paulo, 8:1--79, 1953.
• 22: Eran Halperin , Dror Livnat , Uri Zwick, MAX CUT in cubic graphs, Journal of Algorithms, v.53 n.2, p.169-185, November 2004 [doi>10.1016/j.jalgor.2004.06.001]
• 23: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 24: Johan Håstad , S. Venkatesh, On the advantage over a random assignment, Random Structures & Algorithms, v.25 n.2, p.117-149, September 2004 [doi>10.1002/rsa.20031]
• 25: Howard Karloff, How Good is the Goemans--Williamson MAX CUT Algorithm?, SIAM Journal on Computing, v.29 n.1, p.336-350, Feb. 2000 [doi>10.1137/S0097539797321481]
• 26: R. Karp. Reducibility among combinatorial problems, pages 85--103. Plenum Press, 1972.
• 27: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O’Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM Journal on Computing, v.37 n.1, p.319-357, April 2007 [doi>10.1137/S0097539705447372]
• 28: Subhash Khot , Ryan O'Donnell, SDP gaps and UGC-hardness for MAXCUTGAIN, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.217-226, October 21-24, 2006 [doi>10.1109/FOCS.2006.67]
• 29: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 30: Elchanan Mossel , Ryan O'Donnell , Krzysztof Oleszkiewicz, Noise stability of functions with low in.uences invariance and optimality, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.21-30, October 23-25, 2005 [doi>10.1109/SFCS.2005.53]
• 31: S. Poljak and F. Rendl. Nonpolyhedral relaxations of graph-bisection problems. SIAM J. Opt., 5(3):467--487, 1995.
• 32: S. Poljak and Z. Tuza. The max-cut problem - a survey. In Special Year on Combinatorial Optimization, DIMACS series. AMS, 1995.
• 33: F. Rendl, G. Rinaldi, and A. Wiegele. A branch and bound algorithm for Max-Cut based on combining semidefinite and polyhedral relaxations. In Proc. 12th IPCO, pages 295--309, 2007.
• 34: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 35: Luca Trevisan , Gregory B. Sorkin , Madhu Sudan , David P. Williamson, Gadgets, Approximation, and Linear Programming, SIAM Journal on Computing, v.29 n.6, p.2074-2097, April 2000 [doi>10.1137/S0097539797328847]
• 36: Uri Zwick, Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.679-687, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301431]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
hardness of approximation, max-cut, semidefinite programming