A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS

DOI10.15807/JORSJ.46.164MaRDI QIDQ4446320zbMATH OpenOpenAlexFDO

Authors Masakazu Muramatsu, Tsunehiro Suzuki

Publication date 26 January 2004

Published in Journal of the Operations Research Society of Japan (Search for Journal in Brave)

Full work available at URL https://doi.org/10.15807/jorsj.46.164

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Second order cone programming relaxation for quadratic assignment problems
• Strengthened semidefinite programming relaxations for the max-cut problem.
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Node and edge relaxations of the max-cut problem

Cited in

(10)

• SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances
• Penalized semidefinite programming for quadratically-constrained quadratic optimization
• A simultaneous diagonalization based SOCP relaxation for convex quadratic programs with linear complementarity constraints
• scientific article; zbMATH DE number 1786136 (Why is no real title available?)
• Global convergence of the alternating projection method for the max-cut relaxation problem
• A new global algorithm for max-cut problem with chordal sparsity
• A novel auto-pruned ensemble clustering via SOCP
• A second-order cone cutting surface method: Complexity and application
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem

Describes a project that uses

Uses Software

• SDPA
• SeDuMi

This page was built for publication: A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS

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