4 papers
Near-Optimal Bounds for Parameterized Euclidean k-means
Vincent Cohen-Addad, Karthik C. S., David Saulpic +1
The -means problem is a classic objective for modeling clustering in a metric space. Given a set of points in a metric space, the goal is to find representative points so as…
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
Vincent Cohen-Addad, Karthik C. S., David Saulpic +1
The -median and -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 -me…
Fair Clustering in the Sliding Window Model
Vincent Cohen-Addad, Shaofeng H. -C. Jiang, Qiaoyuan Yang +2
We study streaming algorithms for proportionally fair clustering, a notion originally suggested by Chierichetti et. al. (2017), in the sliding window model. We show that although t…
A Tight VC-Dimension Analysis of Clustering Coresets with Applications
Vincent Cohen-Addad, Andrew Draganov, Matteo Russo +2
We consider coresets for -clustering problems, where the goal is to assign points to centers minimizing powers of distances. A popular example is the -median objective $\sum_…