Block-diagonal semidefinite programming hierarchies for 0/1 programming
Lovasz and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for general 0/1 linear programming problems. In this paper these two constructions are revisited and a new, block-diagonal hierarchy is proposed. It has the advantage of being computationally less costly while being at least as strong as the Lovasz-Schrijver hierarchy. It is applied to the stable set problem and experimental results for Paley graphs are reported.
|, , ,|
|Cornell University Library|
|arXiv.org e-Print archive|
|Semidefinite programming and combinatorial optimization , Spinoza prijs Lex Schrijver|
|Organisation||Networks and Optimization|
Gvozdenovic, N, Laurent, M, & Vallentin, F. (2007). Block-diagonal semidefinite programming hierarchies for 0/1 programming. arXiv.org e-Print archive. Cornell University Library .