scientific article; zbMATH DE number 2196288

MaRDI QIDQ5465121zbMATH OpenFDO

Authors Monique Laurent

Publication date 22 August 2005

zbMATH Keywords

0/1-polytopemax-cutmoment matrixsemidefinite relaxation

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Semidefinite programming (90C22) Combinatorial optimization (90C27)

Recommendations

• Geometry of semidefinite Max-Cut relaxations via matrix ranks
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
• On a positive semidefinite relaxation of the cut polytope
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations

Cited in

(30)

• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Node and edge relaxations of the max-cut problem
• Connection between semidefinite relaxations of the max-cut and stable set problems
• 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 a positive semidefinite relaxation of the cut polytope
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
• Exploring the relationship between max-cut and stable set relaxations
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Bipartite sandwiches: Semidefinite relaxations for maximum biclique
• Strengthened semidefinite programming relaxations for the max-cut problem.
• Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure
• Cutting planes for semidefinite relaxations based on triangle-free subgraphs
• Convex hulls of algebraic sets
• Computation with polynomial equations and inequalities arising in combinatorial optimization
• scientific article; zbMATH DE number 5957371 (Why is no real title available?)
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• scientific article; zbMATH DE number 1182577 (Why is no real title available?)
• Tight cycle relaxations for the cut polytope
• Strict complementarity in semidefinite optimization with elliptopes including the maxcut SDP
• scientific article; zbMATH DE number 5209784 (Why is no real title available?)
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Synchronous values of games
• Convergence of the sum-of-squares hierarchy for quadratic optimization over roots-of-unity
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations

This page was built for publication:

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