A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP

Details A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP

2009-10-11

arxiv.org/abs/0910.2024v2

Computer Science

Data Structures and Algorithms

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A $(\log n)^{Ω(1)}$ integrality gap for the Sparsest Cut SDP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-99218