Strengthened semidefinite programming relaxations for the max-cut problem.

zbMATH Open1049.90051MaRDI QIDQ2768060FDOQ2768060

Authors: Miguel F. Anjos, Henry Wolkowicz 

Publication date: 2001

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

zbMATH Keywords

semidefinite programmingsemidefinite relaxationscut polytopediscrete optimizationLagrangian relaxationmetric polytopeMax-Cut problem

Mathematics Subject Classification ID

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

Cited In (16)

• Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
• Stronger linear programming relaxations of max-cut
• 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
• Title not available (Why is that?)
• A tight semidefinite relaxation of the MAX CUT problem
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B
• Geometry of semidefinite Max-Cut relaxations via matrix ranks
• A novel formulation of the max-cut problem and related algorithm
• Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
• On semidefinite programming relaxations of maximum \(k\)-section
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• A note on the SDP relaxation of the minimum cut problem
• 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

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)