Strengthened semidefinite programming relaxations for the max-cut problem.

MaRDI QIDQ2768060zbMATH OpenFDO

Authors Miguel F. Anjos, Henry Wolkowicz

Publication date 2001

zbMATH Keywords

cut polytopediscrete optimizationLagrangian relaxationMax-Cut problemmetric polytopesemidefinite programmingsemidefinite relaxations

Mathematics Subject Classification ID

Numerical methods based on nonlinear programming (49M37) Semidefinite programming (90C22) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• A tight semidefinite relaxation of the MAX CUT problem
• scientific article; zbMATH DE number 2196288
• Connection between semidefinite relaxations of the max-cut and stable set problems
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations

Cited in

(17)

• Connection between semidefinite relaxations of the max-cut and stable set problems
• Stronger linear programming relaxations of max-cut
• A tight semidefinite relaxation of the MAX CUT problem
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Geometry of semidefinite Max-Cut relaxations via matrix ranks
• On semidefinite programming relaxations of maximum \(k\)-section
• A novel formulation of the max-cut problem and related algorithm
• Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
• A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS
• On the integrality gap of the maximum-cut semidefinite programming relaxation in fixed dimension
• scientific article; zbMATH DE number 5209784 (Why is no real title available?)
• A note on the SDP relaxation of the minimum cut problem
• Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations

Describes a project that uses

Uses Software

• SDPpack

This page was built for publication: Strengthened semidefinite programming relaxations for the max-cut problem.

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