Optimization Online


A copositive programming approach to graph partitioning

Janez Povh (janez.povh***at***guest.arnes.si)
Franz Rendl (franz.rendl***at***uni-klu.ac.at)

Abstract: We consider 3-partitioning the vertices of a graph into sets $S_1, S_2$ and $S_3$ of specified cardinalities, such that the total weight of all edges joining $S_1$ and $S_2$ is minimized. This problem is closely related to several NP-hard problems like determining the bandwidth or finding a vertex separator in a graph. We show that this problem can be formulated as a linear program over the cone of completely positive matrices, leading in a natural way to semidefinite relaxations of the problem. We show in particular that the spectral relaxation introduced by Helmberg et al.\ (1995) can equivalently be formulated as a semidefinite program. Finally we propose a tightened version of this semidefinite program and show on some small instances that this new bound is a significant improvement over the spectral bound.

Keywords: semidefinite programming, copositive programming, graph partitioning problem, bandwidth problem, vertex separator problem

Category 1: Combinatorial Optimization (Approximation Algorithms )

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

Citation: Janez Povh, School for business and management, Na Loko 2, 8000 Novo Mesto, Slovenia and Franz Rendl, Universitaet Klagenfurt, Institut fuer Mathematik, Universitaetsstrasse 65-67, 9020 Klagenfurt, Austria. August 2005.

Download: [Postscript][PDF]

Entry Submitted: 08/03/2005
Entry Accepted: 08/03/2005
Entry Last Modified: 08/03/2005

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 Programming Society