Optimization Online


An efficient semidefinite programming relaxation for the graph partition problem

Renata Sotirov (r.sotirov***at***uvt.nl)

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 [A. Frieze and M. Jerrum. Improved approximation algorithms for max $k$-cut and max bisection. Algorithmica, 18(1):67--81, 1997] for the maximum $k$-cut problem with an additional constraint that involves the restrictions on the subset sizes. Since 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 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

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 08/09/2011
Entry Accepted: 08/09/2011
Entry Last Modified: 09/02/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society