Lovász‐Schrijver Reformulation
Madhur Tulsiani · Wiley Encyclopedia of Operations Research and Management Science · 2011
Abstract We discuss the hierarchies of linear and semidefinite programs defined by Lovász and Schrijver. We describe recent progress on these hierarchies in the contexts of algorithm design, computational complexity, and proof complexity.