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

DOI10.1007/S10589-015-9779-8MaRDI QIDQ5963676zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 23 February 2016

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

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

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)

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.

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

Cites work

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

Cited in

(9)

• The MIN-cut and vertex separator problem
• scientific article; zbMATH DE number 1664574 (Why is no real title available?)
• 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
• Semidefinite programming and eigenvalue bounds for the graph partition problem
• ADMM for the SDP relaxation of the QAP

Describes a project that uses

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)