The integrality gap of the Goemans--Linial SDP relaxation for Sparsest Cut is at least a constant multiple of √(log n)

2017/04/04 by Assaf Naor, Robert Young, Naor, Assaf +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1704.01200

This is an extended abstract that announces results whose complete proofs appear in https://arxiv.org/abs/1701.00620 (though a large part of this extended abstract is material that does not appear in https://arxiv.org/abs/1701.00620). It will appear in the proceedings of STOC 2017

arxiv created 2017/04/04 · arxiv updated 2017/04/06

Abstract

We prove that the integrality gap of the Goemans--Linial semidefinite programming relaxation for the Sparsest Cut Problem is Ω(√(log n)) on inputs with n vertices.

Citations

• Vertical perimeter versus horizontal perimeter

Related

• A (log n)^Ω(1) integrality gap for the Sparsest Cut SDP
• Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low-Dimensional Spaces
• Compression bounds for Lipschitz maps from the Heisenberg group to L₁
• Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
• Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut