A notion of inverse Chvátal rank
Speaker: | Marco di Summa |
---|---|
Affiliation: | University of Padova |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
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.)