Cones of Matrices and Set-Functions and 0–1 Optimization IV: Clique, Odd Hole, Odd Wheel and Odd Antihole Constraints Hold after One Round of N₊Research Paper
The stable set problem (find a largest, or maximum-weight, set of pairwise non-adjacent nodes in a graph) is NP-hard, and its linear programming relaxations have been studied since the 1970s as a test bed for polyhedral combinatorics. Lovász and Schrijver (SIAM J. Optim. 1991) introduced a general lift-and-project procedure for 0–1 programs: lift a…