A (log n)Ω(1) integrality gap for the sparsest cut SDP

Jeff Cheeger; Bruce Kleiner; Assaf Naor

doi:10.1109/FOCS.2009.47

A (log n)^Ω(1) integrality gap for the sparsest cut SDP

Jeff Cheeger, Bruce Kleiner, Assaf Naor

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009
Pages	555-564
Number of pages	10
DOIs	https://doi.org/10.1109/FOCS.2009.47
State	Published - 2009
Event	50th Annual Symposium on Foundations of Computer Science, FOCS 2009 - Atlanta, GA, United States Duration: Oct 25 2009 → Oct 27 2009

Publication series

Name	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)	0272-5428

Other

Other	50th Annual Symposium on Foundations of Computer Science, FOCS 2009
Country/Territory	United States
City	Atlanta, GA
Period	10/25/09 → 10/27/09

Keywords

Heisenberg group
Integrality gap
Metric embeddings
Semidefinite programming
Sparsest cut problem

ASJC Scopus subject areas

General Computer Science

Access to Document

10.1109/FOCS.2009.47

Cite this

A (log n)^Ω(1) integrality gap for the sparsest cut SDP. / Cheeger, Jeff ; Kleiner, Bruce; Naor, Assaf.
Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009. 2009. p. 555-564 5438599 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cheeger, J , Kleiner, B & Naor, A 2009, A (log n)^Ω(1) integrality gap for the sparsest cut SDP. in Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009., 5438599, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 555-564, 50th Annual Symposium on Foundations of Computer Science, FOCS 2009, Atlanta, GA, United States, 10/25/09. https://doi.org/10.1109/FOCS.2009.47

@inproceedings{3c6e178a59964a8c9c7fa453f112520c,

title = "A (log n)Ω(1) integrality gap for the sparsest cut SDP",

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 L1 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 L1 when restricted to cosets of the center.",

keywords = "Heisenberg group, Integrality gap, Metric embeddings, Semidefinite programming, Sparsest cut problem",

author = "Jeff Cheeger and Bruce Kleiner and Assaf Naor",

year = "2009",

doi = "10.1109/FOCS.2009.47",

language = "English (US)",

isbn = "9780769538501",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

pages = "555--564",

booktitle = "Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009",

}

TY - GEN

T1 - A (log n)Ω(1) integrality gap for the sparsest cut SDP

AU - Cheeger, Jeff

AU - Kleiner, Bruce

AU - Naor, Assaf

PY - 2009

Y1 - 2009

N2 - 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 L1 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 L1 when restricted to cosets of the center.

AB - 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 L1 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 L1 when restricted to cosets of the center.

KW - Heisenberg group

KW - Integrality gap

KW - Metric embeddings

KW - Semidefinite programming

KW - Sparsest cut problem

UR - http://www.scopus.com/inward/record.url?scp=77952362220&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77952362220&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2009.47

DO - 10.1109/FOCS.2009.47

M3 - Conference contribution

AN - SCOPUS:77952362220

SN - 9780769538501

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 555

EP - 564

BT - Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009

T2 - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009

Y2 - 25 October 2009 through 27 October 2009

ER -