info:eu-repo/semantics/article
Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope
Fecha
2014-02Registro en:
Bianchi, Silvia Maria; Escalante, Mariana Silvina; Nasini, Graciela Leonor; Tunçel, Levent; Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope; Elsevier Science; Discrete Applied Mathematics; 164; Part 2; 2-2014; 460-469
0166-218X
CONICET Digital
CONICET
Autor
Bianchi, Silvia Maria
Escalante, Mariana Silvina
Nasini, Graciela Leonor
Tunçel, Levent
Resumen
We study Lovász and Schrijver's hierarchy of relaxations based on positive semidefiniteness constraints derived from the fractional stable set polytope. We show that there are graphs G for which a single application of the underlying operator, N+, to the fractional stable set polytope gives a nonpolyhedral convex relaxation of the stable set polytope. We also show that none of the current best combinatorial characterizations of these relaxations obtained by a single application of the N+ operator is exact.