A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming

By Monique Laurent. Mathematics of Operations Research, 2003

471 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Approximation of the Stability Number of a Graph via Copositive Programming (2002, background): “Laurent [11, 12] has recently shown the relationship between these approaches.”
Graphical Models, Exponential Families, and Variational Inference (2008, methodology): “See Laurent [66, 67] for comparison of these sequences in a more general setting.”
Handbook of Satisfiability (2021, methodology): “) A detailed analysis of the connections between the Sherali-Adams, Lovász-Schrijver, and Lasserre frameworks was done by Laurent (191).”
A Combinatorial Approach to Nonlocality and Contextuality (2012, methodology): “We have not implemented any of this since for any particular class of problems, one can construct specialized (hierarchies of) semidefinite relaxations of smaller size [7,64].”
Revisiting two theorems of Curto and Fialkow on moment matrices (2005, background): “Laurent ([21], [22]) gives an alternative proof for these convergence results.”