On the facets of lift-and-project relaxations under graph operations | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional del Litoral | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de Rosario | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de Rosario | |
| dc.contributor.author | Aguilera, Néstor Edgardo | |
| dc.contributor.author | Escalante, Mariana Silvina | |
| dc.contributor.author | Fekete, Pablo Gabriel | |
| dc.date.issued | 2014-02 | |
| dc.description.abstract | We study the behavior of lift-and-project procedures for solving combinatorial optimization problems as described by Lovász and Schrijver (1991) [6] in the context of the stable set problem on graphs. Following the work of Wolsey (1976) [10], Lipták and Lovász (2001) [4] and Lipták and Tunçel (2003) [5], we investigate how to generate facets of the relaxations obtained by these procedures from facets of the relaxations of the original graph, after applying fundamental graph operations. We show our findings for the odd and the star subdivision, the stretching of a node and a new operation defined herein called the clique subdivision of an edge | es |
| dc.description.fil | Fil: Aguilera, Néstor Edgardo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional del Litoral; Argentina | |
| dc.description.fil | Fil: Escalante, Mariana Silvina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario; Argentina | |
| dc.description.fil | Fil: Fekete, Pablo Gabriel. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Aguilera, Néstor Edgardo; Escalante, Mariana Silvina; Fekete, Pablo Gabriel; On the facets of lift-and-project relaxations under graph operations; Elsevier Science; Discrete Applied Mathematics; 164; 2; 2-2014; 360-372 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/30101 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.number | 2 | es |
| dc.journal.pagination | 360-372 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 164 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2012.07.012 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0166218X12002776 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | Operations in Graphs | es |
| dc.subject | Lift-And-Project Operators | es |
| dc.subject | Stable Set | es |
| dc.subject.classification | Matemática Pura | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | On the facets of lift-and-project relaxations under graph operations | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.e0db9f2b-db3b-4536-b554-f3a0dd985abd_A.pdf
- Tamaño:
- 332.59 KB
- Formato:
- Adobe Portable Document Format