A note on the SDP relaxation of the minimum cut problem

DOI10.1007/s10898-022-01235-yzbMath1526.05115OpenAlexW4298005162MaRDI QIDQ6064052

Xinxin Li, Jiageng Wu, Hao Hu

Publication date: 8 November 2023

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-022-01235-y

zbMATH Keywords

minimum cutsemidefinite relaxationfacial reduction

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact algorithm for solving the vertex separator problem
• The MIN-cut and vertex separator problem
• A multilevel bilinear programming algorithm for the vertex separator problem
• A framework for solving VLSI graph layout problems
• Regularizing the abstract convex program
• Exploiting sparsity in primal-dual interior-point methods for semidefinite programming
• Semidefinite programming relaxations for the quadratic assignment problem
• The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
• Semidefinite programming relaxations for the graph partitioning problem
• A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Bandwidth, Vertex Separators, and Eigenvalue Optimization
• A Strictly Contractive Peaceman--Rachford Splitting Method for Convex Programming
• Generalized Nested Dissection
• Applications of a Planar Separator Theorem
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Geometric Separators for Finite-Element Meshes
• Tightness of a New and Enhanced Semidefinite Relaxation for MIMO Detection
• A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP
• A Copositive Programming Approach to Graph Partitioning
• Algorithms and Computation
• Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
• Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs