Introduction to Coresets: Approximated Mean

Alaa Maalouf, Ibrahim Jubran, Dan Feldman

A \emph{strong coreset} for the mean queries of a set $P$ in ${\mathbb{R}}^d$ is a small weighted subset $C\subseteq P$, which provably approximates its sum of squared distances to…