A notion of inverse Chvátal rank
|Speaker:||Marco di Summa|
|Affiliation:||University of Padova|
|Room:||Mathematics & Computer Building (MC) 5158|
The Chvátal rank of a polyhedron Q is the number of times one has to iterate the derivation of the so-called Chvátal closure in order to obtain the integer hull of Q, i.e., the polyhedron P defined as the convex hull of the integer points in Q. This number is known to be always finite for a fixed Q.
In this talk I will reverse this viewpoint by introducing the notion of inverse Chvátal rank: for an integral polyhedron P, the inverse Chvátal rank of P is the supremum of the Chvátal ranks of all polyhedra Q whose integer hull is P. In other words, this number describes how bad the worst linear relaxation of P is.
I will give a characterization of the integral polyhedra for which this value is finite, and discuss bounds on the inverse Chvátal rank for certain classes of integral polyhedra.
(This is joint work with Michele Conforti, Alberto Del Pia, Yuri Faenza and Rolande Grappe.)
200 University Avenue West
Waterloo, ON N2L 3G1