| 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. |