0/1 Polytopes with Quadratic Chvátal Rank
Speaker: | Laura Sanità |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
For
a
polytope
P,
the
Chvátal
closure
P'⊆P
is
obtained
by
simultaneously
strengthening
all
feasible
inequalities
cx≤β
(with
integral
c)
to
cx≤⌊β⌋.
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
P⊆[0,1]n,
then
it
is
known
that
O(n2
log
n)
iterations
always
suffices
(Eisenbrand
and
Schulz
(1999))
and
at
least
(1+1/e-0(1))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
Ω(n2),
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ß.