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

DOI10.1007/s10589-015-9779-8zbMath1360.90263arXiv1401.5170OpenAlexW1648726702WikidataQ57511176 ScholiaQ57511176MaRDI QIDQ5963676

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)

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

zbMATH Keywords

graph partitioningeigenvalue boundslarge scalesemidefinite programming boundsvertex separators

Mathematics Subject Classification ID

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

Related Items

Minimum energy configurations on a toric lattice as a quadratic assignment problem, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, A note on the SDP relaxation of the minimum cut problem, ADMM for the SDP relaxation of the QAP, The MIN-cut and vertex separator problem, A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem

Uses Software

• SDPT3

Cites Work

• Solving semidefinite-quadratic-linear programs using SDPT3
• Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
• A computational study of graph partitioning
• Semidefinite programming relaxations for the quadratic assignment problem
• A projection technique for partitioning the nodes of a graph
• Semidefinite programming relaxations for the graph partitioning problem
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A branch and bound algorithm for the matrix bandwidth minimization
• The variation of the spectrum of a normal matrix
• On Lagrangian Relaxation of Quadratic Matrix Constraints
• Solving quadratic assignment problems using convex quadratic programming relaxations
• Bandwidth, Vertex Separators, and Eigenvalue Optimization
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• On semidefinite programming bounds for graph bandwidth
• A new bound for the quadratic assignment problem based on convex quadratic programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item