Quick and Dirty
Renata Sotirov* and Edwin van Dam
The graph partition is a problem of partitioning of the vertex set of a graph into $k$ disjoint sets of given sizes such that the total weight of edges joining different sets is optimized. In this talk we show how to simplify known semidefinite programming relaxations for the GPP for some special types of graphs so that they can be fast solved. We also compare resulted bounds with the strongest known SDP bounds for the GPP derived also by us.
Mathematics Subject Classification: 90C22 97N60
Keywords: the graph partition problem; semidefinite programming
Minisymposion: Algorithms Based on Semidefinite Optimization