dc.creator | Bianchi, Silvia Maria | |
dc.creator | Escalante, Mariana Silvina | |
dc.creator | Nasini, Graciela Leonor | |
dc.creator | Tunçel, Levent | |
dc.date.accessioned | 2020-01-10T19:17:16Z | |
dc.date.accessioned | 2022-10-15T03:29:48Z | |
dc.date.available | 2020-01-10T19:17:16Z | |
dc.date.available | 2022-10-15T03:29:48Z | |
dc.date.created | 2020-01-10T19:17:16Z | |
dc.date.issued | 2014-02 | |
dc.identifier | 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 | |
dc.identifier | 0166-218X | |
dc.identifier | http://hdl.handle.net/11336/94350 | |
dc.identifier | CONICET Digital | |
dc.identifier | CONICET | |
dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/4340240 | |
dc.description.abstract | 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. | |
dc.language | eng | |
dc.publisher | Elsevier Science | |
dc.relation | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2013.03.028 | |
dc.relation | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X13001765 | |
dc.rights | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | |
dc.rights | info:eu-repo/semantics/restrictedAccess | |
dc.subject | LIFT-AND-PROJECT | |
dc.subject | SEMIDEFINITE PROGRAMMING | |
dc.subject | STABLE SET PROBLEM | |
dc.title | Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope | |
dc.type | info:eu-repo/semantics/article | |
dc.type | info:ar-repo/semantics/artículo | |
dc.type | info:eu-repo/semantics/publishedVersion | |