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" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.