32 citations · 37 across the 13 of their papers we have counts for
14 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_…
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…
Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger +5
We study the data selection problem, whose aim is to select a small representative subset of data that can be used to efficiently train a machine learning model. We present a new d…
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…
An Improved Local Search Algorithm for k-Median
Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu +2
We present a new local-search algorithm for the -median clustering problem. We show that local optima for this algorithm give a -approximation; our result improves up…
A New Coreset Framework for Clustering
Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn
Given a metric space, the -clustering problem consists of finding centers such that the sum of the of distances raised to the power of every point to its closest cen…
Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics
Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic
We consider the classic Facility Location, -Median, and -Means problems in metric spaces of doubling dimension . We give nearly linear-time approximation schemes for each…
On the Local Structure of Stable Clustering Instances
Vincent Cohen-Addad, Chris Schwiegelshohn
We study the classic -median and -means clustering objectives in the beyond-worst-case scenario. We consider three well-studied notions of structured data that aim at charact…