Title: On the hardness of computing the diameter of a polytope
| Speaker: | Laura Sanita |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
The diameter of a polytope P is given by the maximum length of a shortest path between a pair of vertices on P. Giving bounds on the diameter of a polytope is a fundamental research topic in theoretical computer science and discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex Algorithm for solving Linear Programs.
The
diameter
of
a
polytope
has
been
studied
from
many
different
perspectives,
including
a
computational
complexity
point
of
view.
In
particular,
Frieze
and
Teng
in
1994
showed
that
computing
the
diameter
of
a
polytope
is
weakly
NP-hard.
In
this
talk,
we
will
strengthen
this
hardness
result,
by
exploiting
the
structure
of
a
notorious
and
well-studied
polytope
in
the
optimization
community:
the
fractional
matching
polytope.
In
particular,
we
will
give
an
exact
characterization
of
the
diameter
of
this
polytope,
and
then
use
it
to
derive
strong
NP-hardness
(in
fact,
APX-hardness)
for
the
problem
of
computing
the
diameter.