Eigenvalue, Quadratic Programming, and Semidefinite Programming Bounds for a Cut Minimization Problem

Ting Kei Pong, Hao Sun, Ningchuan Wang +1

We consider the problem of partitioning the node set of a graph into $k$ sets of given sizes in order to \emph{minimize the cut} obtained using (removing) the $k$-th set. If the re…