IMAL 13325
INSTITUTO DE MATEMATICA APLICADA DEL LITORAL "DRA. ELEONOR HARBOURE"
Unidad Ejecutora - UE
artículos
Título:
On packing and covering polyhedra of consecutive ones circulant clutters
Autor/es:
N. AGUILERA
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Año: 2009
ISSN:
0166-218X
Resumen:
Building on work by G. Cornuéjols and B. Novick and by L. Trotter, we give different characterizations of contractions of consecutive ones circulant clutters that give back consecutive ones circulant clutters. Based on a recent result by G. Argiroffo and S. Bianchi, we then arrive at characterizations of the vertices of the fractional set covering polyhedron of these clutters. We obtain similar characterizations for the fractional set packing polyhedron using a result by F.B. Shepherd, and relate our findings with similar ones obtained by A. Wagler for the clique relaxation of the stable set polytope of webs. Finally, we show how our results can be used to obtain some old and new results on the corresponding fractional set covering polyhedron using properties of Farey series. Our results do not depend on Lehmans work or blocker/antiblocker duality, as is traditional in the field.
