Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces

Vincent Cohen-Addad, Karthik C. S., David Saulpic +1

The $k$-median and $k$-means clustering objectives are classic objectives for modeling clustering in a metric space. Given a set of points in a metric space, the goal of the $k$-me…