### 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 language | English (US) |
---|---|

Pages (from-to) | 1698-1717 |

Number of pages | 20 |

Journal | SIAM Journal on Optimization |

Volume | 24 |

Issue number | 4 |

DOIs | |

State | Published - Jan 1 2014 |

Externally published | Yes |

### Fingerprint

### Keywords

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

### ASJC Scopus subject areas

- Theoretical Computer Science
- Software

### Cite this

*SIAM Journal on Optimization*,

*24*(4), 1698-1717. https://doi.org/10.1137/13093025X

**Constant factor Lasserre integrality gaps for graph partitioning problems.** / Guruswami, Venkatesan; Sinop, Ali Kemal; Zhou, Yuan.

Research output: Contribution to journal › Article

*SIAM Journal on Optimization*, vol. 24, no. 4, pp. 1698-1717. https://doi.org/10.1137/13093025X

}

TY - JOUR

T1 - Constant factor Lasserre integrality gaps for graph partitioning problems

AU - Guruswami, Venkatesan

AU - Sinop, Ali Kemal

AU - Zhou, Yuan

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

KW - Balanced separator

KW - Integrality gaps

KW - Lasserre semidefinite programming hierarchy

KW - Uniform sparsest cut

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

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

U2 - 10.1137/13093025X

DO - 10.1137/13093025X

M3 - Article

AN - SCOPUS:84919817033

VL - 24

SP - 1698

EP - 1717

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 4

ER -