Friday, June 26, 2015 3:30 pm
-
3:30 pm
EDT (GMT -04:00)
Title: K-route multicuts in graphs
| Speaker: | Laura Sanita |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
We
study
the
k-route
generalizations
of
various
cut
problems,
the
most
general
of
which
is
k-route
multicut,
wherein
we
have
r
source-sink
pairs
and
the
goal
is
to
delete
a
minimum-cost
set
of
edges
to
reduce
the
edge-connectivity
of
every
pair
to
below
k.
We
present
various
approximation
and
hardness
results
that
improve
the
state-of-the-art
for
these
problems
in
several
cases.
Our
algorithms
are
based
on
combinatorial
techniques
and
on
a
new
powerful
region-growing
approach.
Joint
work
with
Guru
Guruganesh
and
Chaitanya
Swamy.