title
Relaxations of Graph Partitioning and Vertex Separator Problems using
Continuous Optimization
pdf file
(work with Hao Sun, Ningchuan Wang)
Abstract:
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.