Title:  Relaxations of Graph Partitioning and Vertex Separator Problems using Continuous Optimization

Both the Graph Partitioning and Vertex Separator problems are hard discrete optimization problems. We look at several approximation techniques. This includes eigenvalue and projected eigenvalue techniques, quadratic programming techniques, and semidefinite programming (SDP). In particular, we show that the SDP relaxation is equivalent to and arises from the Lagrangian relaxation for a particular quadratically constrained quadratic model. Moreover, the bounds obtained by the SDP techniques are the best among the ones we compare.

Joint work with Ting Kei Pong, Hao Sun, and Ningchuan Wang.