TY - GEN

T1 - Sparsest Cut on quotients of the hypercube

AU - Kolla, Alexandra

AU - Lee, James R.

PY - 2011

Y1 - 2011

N2 - We present a simple construction and analysis of an Ω(log logN) integrality gap for the well-known Sparsest Cut semi-definite program (SDP). This holds for the uniform demands version (i.e. edge expansion). The same quantitative gap was proved earlier by Devanur, Khot, Saket, and Vishnoi [STOC 2006], following an integrality gap for non-uniform demands due to Khot and Vishnoi [FOCS 2005]. These previous constructions involve a complicated SDP solution and analysis, while our gap instance, vector solution, and analysis are somewhat simpler and more intuitive. Furthermore, our approach is rather general, and provides a variety of different gap examples derived from quotients of the hypercube. It also illustrates why the lower bound is stuck at Ω(log logN), and why new ideas are needed in order to derive stronger examples.

AB - We present a simple construction and analysis of an Ω(log logN) integrality gap for the well-known Sparsest Cut semi-definite program (SDP). This holds for the uniform demands version (i.e. edge expansion). The same quantitative gap was proved earlier by Devanur, Khot, Saket, and Vishnoi [STOC 2006], following an integrality gap for non-uniform demands due to Khot and Vishnoi [FOCS 2005]. These previous constructions involve a complicated SDP solution and analysis, while our gap instance, vector solution, and analysis are somewhat simpler and more intuitive. Furthermore, our approach is rather general, and provides a variety of different gap examples derived from quotients of the hypercube. It also illustrates why the lower bound is stuck at Ω(log logN), and why new ideas are needed in order to derive stronger examples.

KW - Integrality gap

KW - Semidefinite programming

KW - Sparsest Cut

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

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

M3 - Conference contribution

AN - SCOPUS:84864582027

SN - 9781920682989

T3 - Conferences in Research and Practice in Information Technology Series

SP - 11

EP - 21

BT - Theory of Computing 2011 - Proceedings of the 17th Computing

T2 - Theory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011

Y2 - 17 January 2011 through 20 January 2011

ER -