Integrality gaps for sparsest cut and minimum linear arrangement problems

ABSTRACT

Arora, Rao and Vazirani [2] showed that the standard semi-definite programming (SDP) relaxation of the Sparsest Cut problem with the triangle inequality constraints has an integrality gap of O(√log n). They conjectured that the gap is bounded from above by a constant. In this paper, we disprove this conjecture (referred to as the ARV-Conjecture) by constructing an Ω(log log n) integrality gap instance. Khot and Vishnoi [16] had earlier disproved the non-uniform version of the ARV-Conjecture.A simple "stretching" of the integrality gap instance for the Sparsest Cut problem serves as an Ω(log log n) integrality gap instance for the SDP relaxation of the Minimum Linear Arrangement problem. This SDP relaxation was considered in [6, 11], where it was shown that its integrality gap is bounded from above by O(√log n log log n).

REFERENCES

• 1: Sanjeev Arora , James R. Lee , Assaf Naor, Euclidean distortion and the sparsest cut, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060673]
• 2: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 3: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 4: Jean Bourgain. On lipschitz embeddings of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52:46--52, 1985.
• 5: Jean Bourgain. On the distribution of the fourier spectrum of boolean functions. Israel Journal of Mathematics, 131:269--276, 2002.
• 6: Moses Charikar , Mohammad Taghi Hajiaghayi , Howard Karloff , Satish Rao, l²₂ spreading metrics for vertex ordering problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1018-1027, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109670]
• 7: Shuchi Chawla , Anupam Gupta , Harald Räcke, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, On the Hardness of Approximating Multicut and Sparsest-Cut, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.144-153, June 11-15, 2005 [doi>10.1109/CCC.2005.20]
• 9: Nikhil R Devanur, Subhash Khot, Rishi Saket, and Nisheeth Vishnoi. Integrality gaps for sparsest cut and minimum linear arrangement problems. Manuscript available from http://www.cc.gatech.edu/?nikhil/, 2006.
• 10: Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000 [doi>10.1145/347476.347478]
• 11: Uriel Feige and James Lee. An improved approximation ratio for the minimum linear arrangement problem. Manuscript, 2005.
• 12: Michel X. Goemans, Semidefinite programming in combinatorial optimization, Mathematical Programming: Series A and B, v.79 n.1-3, p.143-161, Oct. 1, 1997 [doi>10.1007/BF02614315]
• 13: M. D. Hansen. Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems. In Annual Symposium on Foundations of Computer Science, number 30, pages 604--610, 1989.
• 14: Jeff Kahn, Gil Kalai, and Nati Linial. The influence of variables on boolean functions. In Annual Symposium on Foundations of Computer Science, number 29, pages 68--80, 1988.
• 15: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 16: 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]
• 17: Robert Krauthgamer , Yuval Rabani, Improved lower bounds for embeddings into L₁, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1010-1017, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109669]
• 18: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 19: Nathan Linial, Finite metric spaces: combinatorics, geometry and algorithms, Proceedings of the eighteenth annual symposium on Computational geometry, p.63-63, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513441]
• 20: Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 21: Satish Rao , Andréa W. Richa, New Approximation Techniques for Some Linear Ordering Problems, SIAM Journal on Computing, v.34 n.2, p.388-404, 2005 [doi>10.1137/S0097539702413197]
• 22: David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory