ABSTRACT: We consider the problem of partitioning the nodes of a graph into k sets of given sizes in order to minimize the cut obtained by removing the k-th set. This problem is closely related to the graph partitioning problem. In this talk, we look at lower and upper bounds obtained from two convex relaxation techniques: the quadratic programming bounds based on recent successful bounds for the quadratic assignment problems, and semidefinite programming bounds obtained via lifting.
speaker: Henry Wolkowicz
Work with: Ting Kei Pong, Hao Sun, Ningchuan Wang