Integrality gaps for sparsest cut and minimum linear arrangement problems

Nikhil R. Devanur, Subhash A. Khot, Rishi Saket, Nisheeth K. Vishnoi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Arora, Rao and Vazirani [2] showed that the standard semi-definite programming (SDP) relaxation of the Sparsest Cut problem with the triangle inequality constraints has an integrality gap of O(√log n). They conjectured that the gap is bounded from above by a constant. In this paper, we disprove this conjecture (referred to as the ARV-Conjecture) by constructing an Ω(log log n) integrality gap instance. Khot and Vishnoi [16] had earlier disproved the non-uniform version of the ARV-Conjecture. A simple "stretching" of the integrality gap instance for the Sparsest Cut problem serves as an Ω(log log n) integrality gap instance for the SDP relaxation of the Minimum Linear Arrangement problem. This SDP relaxation was considered in [6, 11], where it was shown that its integrality gap is bounded from above by O(√log n log log n).

Original languageEnglish (US)
Title of host publicationSTOC'06
Subtitle of host publicationProceedings of the 38th Annual ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages537-546
Number of pages10
ISBN (Print)1595931341, 9781595931344
DOIs
StatePublished - 2006
Event38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States
Duration: May 21 2006May 23 2006

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume2006
ISSN (Print)0737-8017

Other

Other38th Annual ACM Symposium on Theory of Computing, STOC'06
CountryUnited States
CitySeattle, WA
Period5/21/065/23/06

Keywords

  • Algorithms
  • Theory

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Integrality gaps for sparsest cut and minimum linear arrangement problems'. Together they form a unique fingerprint.

Cite this