Block-diagonal semidefinite programming hierarchies for 0/1 programming
| Autor: | Gvozdenovic, N., Laurent, M., Vallentin, F. |
|---|---|
| Rok vydání: | 2007 |
| Předmět: | |
| Zdroj: | Oper. Res. Lett., 37 (2009), 27-31 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.orl.2008.10.003 |
| Popis: | 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 two new, block-diagonal hierarchies are proposed. They have the advantage of being computationally less costly while being at least as strong as the Lovasz-Schrijver hierarchy. Our construction is applied to the stable set problem and experimental results for Paley graphs are reported. Comment: 11 pages, (v2) revision based on suggestions by referee, computation of N+(TH(P_q)) included in Table 2 |
| Databáze: | arXiv |
| Externí odkaz: |
|