Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/43457
Title: Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
Authors: Pong, TK 
Sun, H
Wang, N
Wolkowicz, H
Keywords: Eigenvalue bounds
Graph partitioning
Large scale
Semidefinite programming bounds
Vertex separators
Issue Date: 2016
Publisher: Springer
Source: Computational optimization and applications, 2016, v. 63, no. 2, p. 333-364 How to cite?
Journal: Computational optimization and applications 
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.
URI: http://hdl.handle.net/10397/43457
ISSN: 0926-6003
EISSN: 1573-2894
DOI: 10.1007/s10589-015-9779-8
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

18
Last Week
1
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.