| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143433 | Operations Research Letters | 2009 | 5 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
NebojÅ¡a GvozdenoviÄ, Monique Laurent, Frank Vallentin,