An efficient semidefinite programming relaxation for the graph partition problem

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We derive a new semidefinite programming relaxation for the general graph partition problem (GPP). Our relaxation is based on matrix lifting with matrix variable having order equal to the number of vertices of the graph. We show that this relaxation is equivalent to the Frieze-Jerrum relaxation for the maximum k-cut problem with an additional constraint that involves the restrictions on the subset sizes. Because the new relaxation does not depend on the number of subsets k into which the graph should be partitioned we are able to compute bounds for large k. We compare theoretically and numerically the new relaxation with other semidefinite programming (SDP) relaxations for the GPP. The results show that our relaxation provides competitive bounds and is solved significantly faster than any other known SDP bound for the general GPP.
Original languageEnglish
Pages (from-to)16-30
JournalINFORMS Journal on Computing
Volume26
Issue number1
Early online date14 Mar 2013
DOIs
Publication statusPublished - 2014

Fingerprint

Semidefinite programming
Graph

Keywords

  • graph partition
  • graph equipartition
  • matrix lifting
  • vector lifting
  • semidefinite programming

Cite this

@article{c8826f1d39e547988a445fa0ee544265,
title = "An efficient semidefinite programming relaxation for the graph partition problem",
abstract = "We derive a new semidefinite programming relaxation for the general graph partition problem (GPP). Our relaxation is based on matrix lifting with matrix variable having order equal to the number of vertices of the graph. We show that this relaxation is equivalent to the Frieze-Jerrum relaxation for the maximum k-cut problem with an additional constraint that involves the restrictions on the subset sizes. Because the new relaxation does not depend on the number of subsets k into which the graph should be partitioned we are able to compute bounds for large k. We compare theoretically and numerically the new relaxation with other semidefinite programming (SDP) relaxations for the GPP. The results show that our relaxation provides competitive bounds and is solved significantly faster than any other known SDP bound for the general GPP.",
keywords = "graph partition, graph equipartition, matrix lifting, vector lifting, semidefinite programming",
author = "R. Sotirov",
year = "2014",
doi = "10.1287/ijoc.1120.0542",
language = "English",
volume = "26",
pages = "16--30",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "1",

}

An efficient semidefinite programming relaxation for the graph partition problem. / Sotirov, R.

In: INFORMS Journal on Computing, Vol. 26, No. 1, 2014, p. 16-30.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - An efficient semidefinite programming relaxation for the graph partition problem

AU - Sotirov, R.

PY - 2014

Y1 - 2014

N2 - We derive a new semidefinite programming relaxation for the general graph partition problem (GPP). Our relaxation is based on matrix lifting with matrix variable having order equal to the number of vertices of the graph. We show that this relaxation is equivalent to the Frieze-Jerrum relaxation for the maximum k-cut problem with an additional constraint that involves the restrictions on the subset sizes. Because the new relaxation does not depend on the number of subsets k into which the graph should be partitioned we are able to compute bounds for large k. We compare theoretically and numerically the new relaxation with other semidefinite programming (SDP) relaxations for the GPP. The results show that our relaxation provides competitive bounds and is solved significantly faster than any other known SDP bound for the general GPP.

AB - We derive a new semidefinite programming relaxation for the general graph partition problem (GPP). Our relaxation is based on matrix lifting with matrix variable having order equal to the number of vertices of the graph. We show that this relaxation is equivalent to the Frieze-Jerrum relaxation for the maximum k-cut problem with an additional constraint that involves the restrictions on the subset sizes. Because the new relaxation does not depend on the number of subsets k into which the graph should be partitioned we are able to compute bounds for large k. We compare theoretically and numerically the new relaxation with other semidefinite programming (SDP) relaxations for the GPP. The results show that our relaxation provides competitive bounds and is solved significantly faster than any other known SDP bound for the general GPP.

KW - graph partition

KW - graph equipartition

KW - matrix lifting

KW - vector lifting

KW - semidefinite programming

U2 - 10.1287/ijoc.1120.0542

DO - 10.1287/ijoc.1120.0542

M3 - Article

VL - 26

SP - 16

EP - 30

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 1

ER -