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

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

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)

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

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)