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

Ting Pong (), Hao Sun (), Ningchuan Wang () and Henry Wolkowicz ()

Computational Optimization and Applications, 2016, vol. 63, issue 2, 333-364

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. Copyright Springer Science+Business Media New York 2016

Keywords: Vertex separators; Eigenvalue bounds; Semidefinite programming bounds; Graph partitioning; Large scale; 05C70; 15A42; 90C22; 90C27; 90C59 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-015-9779-8 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:63:y:2016:i:2:p:333-364

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-015-9779-8

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().