Linear Programming Relaxations for Steiner Trees
| Speaker: | Dan McQuillan |
|---|---|
| Affiliation: | Norwich University |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
Given a set T of terminal vertices in an undirected weighted graph, the Steiner tree problem is to find the cheapest tree containing T using possibly some other vertices of the graph.
This
problem
is
a
classical
NP-hard
combinatorial
optimization
problems,
and
we
are
interested
in
designing
efficient
approximation
algorithms.
In
particular,
we
investigate
the
technique
of
designing
LP
relaxations
of
an
IP
for
the
problem
and
studying
their
integrality
gaps
(the
ratio
of
the
value
of
the
IP
to
the
LP).
In
this
talk,
I
will
survey
the
various
relaxations
that
have
been
studied
for
the
problem,
and
point
out
their
successes
or
the
lack
thereof
in
designing
approximation
algorithms.
We
will
talk
about
old,
new
and
fresh
off
the
oven
developments.