Abstract

Semidefinite Programming for Graph Partitioning with Preferences
Suely Oliveira - Department of Computer Science, The University of Iowa
David Stewart - Department of Mathematics, The University of Iowa
Takako Soma - Department of Computer Science, The University of Iowa

Parallel data distribution can be modeled as a Graph Partitioning
Problem where we wish to divide a graph into subgraphs with roughly
equal number of nodes with a mininum number of edges crossing
between the subgraphs. This is a well-known NP-complete problem 
so heuristics need to be used. 
Relaxations of the discrete optimization problem include
Spectral graph partitioning and a Semidefinite Programming (SDP) 
relaxation.
In recursive Graph Partitioning an edge crossing between two sets 
can not affect the later partitioning of either set.
This problem can be addressed by constructing an optimization 
problem  which includes preferences associated with each vertex.
This is called Graph Partitioning with Preferences (GPP).
The straightforward relaxation of GPP corresponds to an 
extended eigenvalue problem.
In this paper we developed a SDP 
relaxation for GPP and have 
designed a subspace algorithm for the SDP relaxation.
Last update: Wed Jun 12 14:26:53 2002 WEST