Semidefinite Programming and Graph Equipartition
Stefan E. Karisch and Franz Rendl
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.
Report 302 - CDLDO 55, Department of Mathematics,
Graz University of Technology, Graz, Austria, December 1995.
Contact: karisch@fmatbds02.tu-graz.ac.at
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)