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

DOI10.1007/S10589-015-9779-8zbMATH Open1360.90263DBLPjournals/coap/PongSWW16arXiv1401.5170OpenAlexW1648726702WikidataQ57511176 ScholiaQ57511176MaRDI QIDQ5963676FDOQ5963676

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

Publication date: 23 February 2016

Published in: Computational Optimization and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1401.5170

Recommendations

• The MIN-cut and vertex separator problem
• Semidefinite programming and eigenvalue bounds for the graph partition problem
• An efficient semidefinite programming relaxation for the graph partition problem
• A Copositive Programming Approach to Graph Partitioning
• Algorithms for graph partitioning problems by means of eigenspace relaxations

zbMATH Keywords

graph partitioninglarge scaleeigenvalue boundsvertex separatorssemidefinite programming bounds

Mathematics Subject Classification ID

Quadratic programming (90C20) Programming involving graphs or networks (90C35) Semidefinite programming (90C22)

Cites Work

• Disciplined convex programming
• Solving semidefinite-quadratic-linear programs using SDPT3
• Title not available (Why is that?)
• Combinatorial matrix theory
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• The variation of the spectrum of a normal matrix
• Title not available (Why is that?)
• Semidefinite programming relaxations for the quadratic assignment problem
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A branch and bound algorithm for the matrix bandwidth minimization
• On semidefinite programming bounds for graph bandwidth
• Semidefinite programming relaxations for the graph partitioning problem
• Title not available (Why is that?)
• A computational study of graph partitioning
• Approximating non-convex quadratic programs by semidefinite and copositive programming
• On Lagrangian relaxation of quadratic matrix constraints
• Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
• Solving quadratic assignment problems using convex quadratic programming relaxations
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• A new bound for the quadratic assignment problem based on convex quadratic programming
• A projection technique for partitioning the nodes of a graph
• Bandwidth, Vertex Separators, and Eigenvalue Optimization
• Title not available (Why is that?)

Cited In (8)

• The MIN-cut and vertex separator problem
• Title not available (Why is that?)
• Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
• A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem
• Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem
• Minimum energy configurations on a toric lattice as a quadratic assignment problem
• A note on the SDP relaxation of the minimum cut problem
• ADMM for the SDP relaxation of the QAP

Uses Software

• SDPT3

This page was built for publication: Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963676)