Índices N y N_+ para el polítopo de conjuntos estables asociado a ciertas familias de antiwebs
##plugins.themes.bootstrap3.article.main##
Resumen
Resumen: En el presente artículo, revisamos los operadores N y N_+ de levantamiento y proyección (lift-and-project) definidos porLovász y Schrijver, así como su aplicación al polítopo de conjuntos estables de un grafo. Posteriormente, estudiamos las propiedades de los índices N y N_+ asociados a estos operadores sobre la clase particular de grafos de las antiwebs. Demostramos que el índice N_+ de cualquier antiweb es igual 1, y presentamos un esquema constructivo que permite acotar elvalor del índice Npara ciertas familias de antiwebs.
Abstract: We reviewthe lift-and-project N and N+ operators defined by Lov´asz and Schrijver [3], aswell as their application
to the stable set polytope of a graph.We study the properties of the related N and N+ indices on the particular graph
class of antiwebs. We show that the N+ index related to an antiweb is equal to 1, and we propose a constructive
scheme to bound from above the N index related to certain families of antiwebs.
Descargas
Descargas
Detalles del artículo
Citas
V. Chvátal. Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math, pages 205-337, 1973.
EugeniaHolm, Luis M. Torres, and Annegret Wagler. On the Chvátal-rank of linear relaxations of the stable set polytope. International Transactions in Operational Research, pages 827-849, 2010.
László Lovász and Alexander Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM Journal of Optimization, pages 166-190, 1991.
Maribel Montenegro. Índices N y N+ del polítopo de conjuntos estables asociado a ciertas familias de antiwebs. Undergraduate thesis, Escuela Politécnica Nacional, 2012.
Leslie E. Trotter, Jr. A class of facet producing graphs for vertex packing polyhedra. Disc. Math., (12):373-388, 1975.
Annegret Wagler. Antiwebs are rank-perfect. 4OR, 2(2):149-152, 2004.