Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem

Ting Kei Pong, Hao Sun, Ningchuan Wang, Henry Wolkowicz

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

We consider the problem of partitioning the node set of a graph into k sets of given sizes in order to minimize the cut obtained using (removing) the kth 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 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 huge problems that illustrate the efficiency of the bounds in terms of strength and time.
Original languageEnglish
Pages (from-to)333-364
Number of pages32
JournalComputational Optimization and Applications
Volume63
Issue number2
DOIs
Publication statusPublished - 1 Mar 2016

Keywords

  • Eigenvalue bounds
  • Graph partitioning
  • Large scale
  • Semidefinite programming bounds
  • Vertex separators

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Cite this