Near-Optimal Quantum Coreset Construction Algorithms for Clustering

Yecheng Xue, Xiaoyu Chen, Tongyang Li +1

$k$-Clustering in ${\mathbb{R}}^d$ (e.g., $k$-median and $k$-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the class…