A (log n)^Ω(1) integrality gap for the Sparsest Cut SDP

2009/10/11 by Jeff Cheeger, Bruce Kleiner, Cheeger, Jeff +3
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #cs.DS #math.FA

paper · pdf · doi:10.48550/arxiv.0910.2024

arxiv created 2009/11/18 · arxiv updated 2009/12/01

Abstract

We show that the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem with general demands has integrality gap (log n)^Ω(1). This is achieved by exhibiting n-point metric spaces of negative type whose L₁ distortion is (log n)^Ω(1). Our result is based on quantitative bounds on the rate of degeneration of Lipschitz maps from the Heisenberg group to L₁ when restricted to cosets of the center.

Related

• The integrality gap of the Goemans--Linial SDP relaxation for Sparsest Cut is at least a constant multiple of √(log n)
• Compression bounds for Lipschitz maps from the Heisenberg group to L₁
• Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low-Dimensional Spaces
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into ℓ₁
• Euclidean distortion and the Sparsest Cut