Optimization Online


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

Ting Kei Pong (tkpong***at***cs.ubc.ca)
Hao Sun (hao_sun***at***live.com)
Ningchuan Wang (wangningchuan1987***at***hotmail.com)
Henry Wolkowicz (hwolkowicz***at***uwaterloo.ca)

Abstract: 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 resulting cut has value $0$, then we have obtained a vertex separator. This problem is closely related to the graph partitioning problem. In fact, the model we use is the same as that for the graph partitioning problem except for a different \emph{quadratic} objective function. We look at known and new bounds obtained from various relaxations for this NP-hard problem. This includes: the standard eigenvalue bound, projected eigenvalue bounds using both the adjacency matrix and the Laplacian, quadratic programming (QP) bounds based on recent successful QP bounds for the quadratic assignment problems, and semidefinite programming bounds. We include numerical tests for large and \emph{huge} problems that illustrate the efficiency of the bounds in terms of strength and time.

Keywords: vertex separators, eigenvalue bounds, semidefinite programming bounds, graph partitioning, large scale.

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: University of Waterloo Department of Combinatorics & Optimization Waterloo, Ontario N2L 3G1, Canada Research Report, January, 2014

Download: [PDF]

Entry Submitted: 01/20/2014
Entry Accepted: 01/21/2014
Entry Last Modified: 11/18/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society