Title: Submodular function maximization via the multilinear relaxation and contention resolution schemes
| Speaker: | Sharat Ibrahimpur |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
I
will
present
a
general
framework
for
maximizing
a
nonnegative
submodular
set
function
$f$ subject
to
a
variety
of
packing
type
constraints
including
multiple
matroid
constraints,
knapsack
constraints,
and
their
intersections.
Two takeaways
from
this
talk
will
be:
(i)
a
constant
factor
approximation
algorithm
to
maximize
the
multilinear
extension
$F$
of
$f$
over
a
solvable
down-closed
polytope;
and
(ii)
an
effective
rounding
strategy
based
on
contention
resolution
schemes.
In
particular,
we
will
see
how
contention
resolution
schemes
for
different
polytopes can
be
combined
to
handle
the
intersection
of
different
constraints.
Based
on
the
work
of
Chekuri,
Vondrak,
and
Zenklusen
by
the
same
title.