The Power of Deferral: Maintaining the Constant-Competitive Steiner Tree a result by Albert Gu, Anupam Gupta, Amit Kumar
| Speaker: | Kanstantsin Pashkovich |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computing Building (MC) 6486 |
Abstract:
Doors will open at 4:15 p.m. As usual we will have 15 mins for socializing and for eating pizza before the talk starts (at 4:30 p.m. sharp).
In
the
online
Steiner
tree
problem,
a
sequence
of
points
is
revealed
one-by-one.
When
a
new
point
arrives,
we
have
time
to
add
only
a
single
edge
connecting
this
new
point
to
the
previously
arrived
points,
and
we
want
to
minimize
the
total
length
of
edges
added.
In
this
case
a
greedy
algorithm
maintains
a
tree
of
the
cost
O(log
n)
times
the
cost
of
an
optimal
Steiner
tree,
and
this
is
the
best
possible.
If
we
modify
the
online
Steiner
tree
problem
so
that
after
an
arrival
of
a
new
point
we
have
a
possibility
not
only
to
introduce
a
new
edge
but
also
to
change
one
of
the
previously
bought
edges,
then
Gu,
Gupta
and
Kumar
provide
an
algorithm,
which
maintains
a
tree
of
a
total
cost
equal
constant
times
the
cost
of
an
optimal
Steiner
tree.
The
presentation
will
be
based
on
the
following
manuscript:
The
Power
of
Deferral:
Maintaining
a
Constant-Competitive
Steiner
Tree
Online.
For more information about our reading group, please visit our webpage.