Friday, 16:15 - 16:40 h, Room: H 3004


Luis Torres
On the Chvátal-closure of the fractional set covering polyhedron of circulant matrices

Coauthor: Paola Tolomei


The set covering polyhedron Q*(Cnk) related to circulant 0,1-matrices has been the object of several recent studies. It has been conjectured that the Chvátal-rank of its fractional relaxation Q(Cnk) is equal to 1. In 2009, Argiroffo and Bianchi characterized all vertices of Q(Cnk). Building upon their characterization, we investigate the first Chvátal-closure of this polyhedron. Our aim is to obtain a complete linear description, by considering the integral generating sets of the cones spanned by the normal vectors of the facets containing each vertex of Q(Cnk). In this talk we present the results obtained so far for some classes of vertices. In particular, our construction yields a counterexample to a conjecture that all facets of Q*(Cnk) are given by boolean, nonnegative, and so-called minor inequalities having only coefficients in {1,2}. At the same time, we motivate why a weaker version of this conjecture might still hold.


Talk 3 of the invited session Fri.3.H 3004
"Packing, covering and domination II" [...]
Cluster 2
"Combinatorial optimization" [...]


  payday loan . What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.