|
For a polytope
$P$,
the Chvátal closure
is
obtained by simultaneously strengthening all feasible inequalities
(with integral $c$) to
 .
The
number of iterations of this procedure that are needed until the
integral hull of $P$ is reached is called the Chvátal rank.
If
 ,
then it is known that
)
iterations always suffices (Eisenbrand and Schulz (1999)) and at least
)n)
iterations are sometimes needed (Pokutta and Stauffer (2011)), leaving
a huge gap between lower and upper bounds.
We prove that there is a polytope contained in the 0/1 cube that has
Chvátal rank
) ,
closing the gap up to a logarithmic
factor.
In fact, even a superlinear lower bound was mentioned as an open
problem by numerous authors.
Joint work with Thomas Rothvoß
|