A note on the SDP relaxation of the minimum cut problem

DOI10.1007/S10898-022-01235-YMaRDI QIDQ6064052zbMATH OpenOpenAlexFDO

Authors Hao Hu, Xin-Xin Li, Jiageng Wu

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

facial reductionminimum cutsemidefinite relaxation

Mathematics Subject Classification ID

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

Recommendations

• A tight semidefinite relaxation of the MAX CUT problem
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Strengthened semidefinite programming relaxations for the max-cut problem.
• A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem
• Geometry of semidefinite Max-Cut relaxations via matrix ranks

Cites work

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

Cited in

(2)

• On the linear relaxation of the \(s-t\)-cut problem with budget constraints
• scientific article; zbMATH DE number 5209784 (Why is no real title available?)

This page was built for publication: A note on the SDP relaxation of the minimum cut problem

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