Title: Changing bases: multistage optimization for matroids and matchings
| Speaker: | Andre Linhares |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract:
In
the
Multistage
Matroid
Maintenance
problem,
we
want
to
maintain
a
(changing)
base
B
of
a
(fixed)
matroid
M
over
a
sequence
of
time
steps.
Each
element
e
of
M
has
a
fixed
acquisition
cost,
which
is
charged
each
time
e
enters
B,
and
a
per
period
cost,
which
changes
over
time
and
is
charged
at
each
time
step
in
which
e
is
in
B.
The
goal
is
to
minimize
the
sum
of
acquisition
and
per
period
costs.
Using
randomized
LP-rounding,
the
authors
obtained
an
O(log
m)-approximation
algorithm
for
the
offline
version
of
the
problem
and
an
O(log
m
log
r)-competitive
algorithm
for
the
online
version,
where
m
and
r
denote
the
number
of
elements
and
the
rank
of
M,
respectively.
The
presentation
will
be
based
on
the
following
manuscript:
http://arxiv.org/abs/1404.3768
For
more
information
about
our
reading
group,
please
visit
our
webpage
http://www.math.uwaterloo.ca/~k2georgi/reading.htm