  


A copositive programming approach to graph partitioning
Janez Povh (janez.povhguest.arnes.si) Abstract: We consider 3partitioning 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 NPhard 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 (Semidefinite 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 6567, 9020 Klagenfurt, Austria. August 2005. Download: [Postscript][PDF] Entry Submitted: 08/03/2005 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  