4 citations · 5 across the 11 of their papers we have counts for
10 papers · 1 filter
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…
Sensitivity Sampling for -Means: Worst Case and Stability Optimal Coreset Bounds
Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu +2
Coresets are arguably the most popular compression paradigm for center-based clustering objectives such as -means. Given a point set , a coreset is a small, weighted summ…
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
In all state-of-the-art sketching and coreset techniques for clustering, as well as in the best known fixed-parameter tractable approximation algorithms, randomness plays a key rol…
Streaming Euclidean -median and -means with Space
Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
We consider the classic Euclidean -median and -means objective on data streams, where the goal is to provide a -approximation to the optimal -median or $k…
The Power of Uniform Sampling for Coresets
Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H. -C. Jiang +4
Motivated by practical generalizations of the classic -median and -means objectives, such as clustering with size constraints, fair clustering, and Wasserstein barycenter, we…
Towards Optimal Lower Bounds for k-median and k-means Coresets
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic +1
Given a set of points in a metric space, the -clustering problem consists of finding a set of points called centers, such that the sum of distances raised to the power o…