4 citations · 4 across the 3 of their papers we have counts for
4 papers
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…
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…