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.
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 | |
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 | United States |
City | Atlanta, GA |
Period | 10/25/09 → 10/27/09 |
All Science Journal Classification (ASJC) codes
- Computer Science(all)
Keywords
- Heisenberg group
- Integrality gap
- Metric embeddings
- Semidefinite programming
- Sparsest cut problem