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 |
Issue Date: | Mar-2016 | Source: | Computational optimization and applications, Mar. 2016, v. 63, no. 2, p. 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. | Keywords: | Eigenvalue bounds Graph partitioning Large scale Semidefinite programming bounds Vertex separators |
Publisher: | Springer | Journal: | Computational optimization and applications | ISSN: | 0926-6003 | EISSN: | 1573-2894 | DOI: | 10.1007/s10589-015-9779-8 | Rights: | © Springer Science+Business Media New York 2015 This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use (https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms), but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10589-015-9779-8 |
| Appears in Collections: | Journal/Magazine Article |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Pong_Eigenvalue_Quadratic_Programming.pdf | Pre-Published version | 797.97 kB | Adobe PDF | View/Open |
Access
View full-text via PolyU eLinks 
Page views
77
Last Week
1
1
Last month
Citations as of Jun 4, 2023
Downloads
14
Citations as of Jun 4, 2023
SCOPUSTM
Citations
6
Last Week
0
0
Last month
Citations as of Jun 2, 2023
WEB OF SCIENCETM
Citations
5
Last Week
0
0
Last month
Citations as of Jun 1, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.