A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem

DOI10.1007/S10589-020-00261-4MaRDI QIDQ2028477zbMATH OpenOpenAlexFDO

Authors Xin-Xin Li, Ting Kei Pong, Hao Sun, Henry Wolkowicz

Publication date 1 June 2021

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

Full work available at URL https://doi.org/10.1007/s10589-020-00261-4

zbMATH Keywords

graph partitioningvertex separatorsemidefinite relaxationdoubly nonnegative relaxationfacial reductionmin-cutpeaceman-Rachford splitting method

Mathematics Subject Classification ID

Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Semidefinite programming (90C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The MIN-cut and vertex separator problem
• A strictly contractive Peaceman-Rachford splitting method for convex programming
• A modified strictly contractive peaceman-Rachford splitting method for multi-block separable convex programming
• Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
• Application of the strictly contractive Peaceman-Rachford splitting method to multi-block separable convex programming

Cites work

• scientific article; zbMATH DE number 991436 (Why is no real title available?)
• scientific article; zbMATH DE number 1266748 (Why is no real title available?)
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A multilevel bilinear programming algorithm for the vertex separator problem
• A semidefinite programming approach to side chain positioning with new rounding strategies
• A strictly contractive Peaceman-Rachford splitting method for convex programming
• ADMM for the SDP relaxation of the QAP
• ADMM_QAP
• An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in R^n
• An exact algorithm for solving the vertex separator problem
• Bandwidth, vertex separators, and eigenvalue optimization
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Convergence study on the symmetric version of ADMM with larger step sizes
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
• Probing the Pareto frontier for basis pursuit solutions
• Regularity and Stability for Convex Multivalued Functions
• 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

Cited in

(6)

• Partitioning through projections: strong SDP bounds for large graph partition problems
• A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAP
• A new stopping criterion for Eckstein and Bertsekas's generalized alternating direction method of multipliers
• Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs
• A strengthened SDP relaxation for quadratic optimization over the Stiefel manifold
• A note on the SDP relaxation of the minimum cut problem

Describes a project that uses

Uses Software

• ADMM_QAP
• SPGL1
• Mosek

This page was built for publication: A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative 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 Q2028477)