Title: Stability Yields a PTAS for k-Median and k-Means Clustering
| Speaker: | Adam Brown |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
Previously,
we
have
seen
a
variety
of
approximation
methods
for
k-median,
and
last
week
we
saw
that
assumptions
on
the
structure
of
our
clustering
instances
can
lead
to
better
guarantees.
In
their
work
of
the
same
title,
Pranjal
Awasthi,
Avrim
Blum,
and
Or
Sheffet
introduce
the
notion
of
weak
deletion
stability
for
k-means
and
k-median
instances
and
use
this
assumption
to
obtain
a
PTAS.
A
k-median
instance
is
weak
deletion
stable
if
for
every
pair
of
clusters
in
an
optimal
clustering
when
we
reassign
all
points
in
one
to
the
other
this
increases
the
objective
cost
by
a
factor
of
at
least
(1+\alpha)
for
some
constant
\alpha
>
0.
I
will
present
their
algorithm,
which
obtains
a
(1
+
\epsilon)-approximation
for
such
k-median
instances,
and
discuss
how
the
technique
is
extended
to
k-means