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