Constant factor Lasserre integrality gaps for graph partitioning problems

Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou

Research output: Contribution to journalArticlepeer-review

Abstract

Partitioning the vertices of a graph into two roughly equal parts while minimizing the number of edges crossing the cut is a fundamental problem (called balanced separator) that arises in many settings. For this problem, and variants such as the uniform sparsest cut problem where the goal is to minimize the fraction of pairs on opposite sides of the cut that are connected by an edge, there are large gaps between the known approximation algorithms and nonapproximability results. While no constant factor approximation algorithms are known, even APX-hardness is not known either. In this work we prove that for balanced separator and uniform sparsest cut, semidefinite programs from the Lasserre hierarchy (which are the most powerful relaxations studied in the literature) have an integrality gap bounded away from 1, even for Ω(n) levels of the hierarchy. This complements recent algorithmic results in Guruswami and Sinop [Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011, pp. 482-491] which used the Lasserre hierarchy to give an approximation scheme for these problems (with runtime depending on the spectrum of the graph). Along the way, we make an observation that simplifies the task of lifting "polynomial constraints" (such as the global balance constraint in balanced separator) to higher levels of the Lasserre hierarchy.

Original languageEnglish (US)
Pages (from-to)1698-1717
Number of pages20
JournalSIAM Journal on Optimization
Volume24
Issue number4
DOIs
StatePublished - Jan 1 2014
Externally publishedYes

Keywords

  • Balanced separator
  • Integrality gaps
  • Lasserre semidefinite programming hierarchy
  • Uniform sparsest cut

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software

Fingerprint Dive into the research topics of 'Constant factor Lasserre integrality gaps for graph partitioning problems'. Together they form a unique fingerprint.

Cite this