Fully Dynamic k-Means Coreset in Near-Optimal Update Time
<|reference_start|>Fully Dynamic k-Means Coreset in Near-Optimal Update Time: We study in this paper the problem of maintaining a solution to $k$-median and $k$-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of $\tilde O(k)$ in general metric spaces, which reduces to $\tilde O(d)$ in the Euclidean space $\mathbb{R}^d$. The query time is $O(k^2)$ in general metrics, and $O(kd)$ in $\mathbb{R}^d$.   To maintain a constant-factor approximation for $k$-median and $k$-means clustering in Euclidean space, this directly leads to an algorithm update time $\tilde O(d)$, and query time $\tilde O(kd + k^2)$. To maintain a $O(polylog~k)$-approximation, the query time is reduced to $\tilde O(kd)$.<|reference_end|>
@article{la tour2024fully,
    title={Fully Dynamic k-Means Coreset in Near-Optimal Update Time},
    author={Max Dupr'e la Tour, Monika Henzinger, David Saulpic},
    journal={arXiv preprint arXiv:2406.19926},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.19926},
    primaryClass={cs.DS}
}