We consider the problem of partitioning the set of nodes of a graph G into k sets ofgiven sizes in order to minimize the cut obtained after removing the k-th set. This is avariant of the well-known vertex separator problem that has applications in e.g., numericallinear algebra. This problem is well studied and there are many lower bounds such as:the standard eigenvalue bound; projected eigenvalue bounds using both the adjacencymatrix and the Laplacian; quadratic programming (QP) bounds derived from imitatingthe (QP) bounds for the quadratic assignment problem; and semidefinite programming(SDP) bounds. For the quadratic assignment problem, a recent paper of [8] had greatsuccess from applying the ADMM (altenating direction method of multipliers) to the SDPrelaxation. We consider the SDP relaxation of the vertex separator problem and theapplication of the ADMM method in solving the SDP. The main advantage of the ADMMmethod is that optimizing over the set of doubly non-negative matrices is about as difficultas optimizing over the set of positive semidefinite matrices. Enforcing the non-negativityconstraint gives us a clear improvement in the quality of bounds obtained. We implementboth a high rank and a nonconvex low rank ADMM method, where the difference is thechoice of rank of the projection onto the semidefinite cone. As for the quadratic assignmentproblem, though there is no theoretical convergence guarantee, the nonconvex approachalways converges to a feasible solution in practice.
PDF
download
878987797
028-85220240
