A copositive programming approach to graph partitioning
Janez Povh (janez.povhguest.arnes.si)
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.
Entry Submitted: 08/03/2005
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|