Semidefinite programming and graph equipartition
Stefan E. Karisch, Franz Rendl · 1998
Semidefinite relaxations are used to approximate the problem of partitioning a graph into equally sized components. The relaxations extend previous eigenvalue based models, and combine semidefinite and polyhedral approaches. Computational results on graphs with several hundred vertices are given, and indicate that semidefinite relaxations approximate the equipartition problem quite well.