| Article ID: | iaor20102929 |
| Volume: | 37 |
| Issue: | 1 |
| Start Page Number: | 27 |
| End Page Number: | 31 |
| Publication Date: | Jan 2009 |
| Journal: | Operations Research Letters |
| Authors: | Laurent Monique, Gvozdenovi Neboja, Vallentin Frank |
| Keywords: | graphs |
Lovász and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for 0/1 linear programming problems. We revisit these two constructions and propose two new, block-diagonal hierarchies, which are at least as strong as the Lovász–Schrijver hierarchy, but less costly to compute. We report experimental results for the stable set problem of Paley graphs.