Title: On the minimum-cost chain-constrained spanning tree problem
| Speaker: | Andre Linhares |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
We
present
a
bicriteria
approximation
algorithm
for
the
problem
of
finding
a
minimum-cost
spanning
tree
in
a
graph
subject
to
degree
constraints
on
a
family
of
vertex
sets
forming
a
chain.
We
show
that
by
using
Lagrangean
relaxation,
one
can
decompose
the
problem
into
uniform-cost
subproblems,
that
can
then
be
handled
by
techniques
that
had
previously
been
applied
to
the
unweighted
version
of
the
problem.
The
algorithm
proposed
finds
a
spanning
tree
that
violates
the
degree
constraints
by
at
most
a
constant
factor
and
whose
cost
is
within
a
constant
factor
of
that
of
an
optimal
feasible
spanning
tree.
Joint
work
with
Chaitanya
Swamy.
The
presentation
will
be
based
on
the
following
manuscript
http://link.springer.com/chapter/10.1007%2F978-3-642-36694-9_28
For
more
information
about
our
reading
group,
please
visit
our
webpage
http://www.math.uwaterloo.ca/~deolivei/reading.htm