Universal Weak Coreset
Ragesh Jaiswal Amit Kumar
Coresets for $k$-means and $k$-median problems yield a small summary of the
data, which preserve the clustering cost with respect to any set of $k$
centers. Recently coresets have also been constructed for constrained $k$-means
and $k$-median problems. However, the notion of coresets has the drawback that
(i) they can only be applied in settings where the input points are allowed to
have weights, and (ii) in general metric spaces, the size of the coresets can
depend logarithmically on the number of points. The notion of weak coresets,
which have less stringent requirements than coresets, has been studied in the
context of classical $k$-means and $k$-median problems. A weak coreset is a
pair $(J,S)$ of subsets of points, where $S$ acts as a summary of the point set
and $J$ as a set of potential centers. This pair satisfies the properties that
(i) $S$ is a good summary of the data as long as the $k$ centers are chosen
from $J$ only, and (ii) there is a good choice of $k$ centers in $J$ with cost
close to the optimal cost. We develop this framework, which we call universal
weak coresets, for constrained clustering settings. In conjunction with recent
coreset constructions for constrained settings, our designs give greater data
compression, are conceptually simpler, and apply to a wide range of constrained
$k$-median and $k$-means problems.