The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling

DOI10.1016/J.ORL.2007.10.006zbMath1152.90555OpenAlexW1988044523MaRDI QIDQ943789

Kevin K. H. Cheung

Publication date: 10 September 2008

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2007.10.006

zbMATH Keywords

semidefinite programmingscalingbinary programmingequivalent relaxation

Mathematics Subject Classification ID

Semidefinite programming (90C22) Boolean programming (90C09)

Cites Work

• Connection between semidefinite relaxations of the max-cut and stable set problems
• Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lovász--Schrijver Lift-and-Project Procedure
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Fixing Variables in Semidefinite Relaxations
• Hadamard determinants Möbius functions, and the chromatic number of a graph
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope

This page was built for publication: The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling