32 citations · 63 across the 14 of their papers we have counts for
17 papers
A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum Clustering
Karthik C. S., Euiwoong Lee, Yuval Rabani +2
Metric -minsum clustering is a simple, natural, appealing density-based clustering criterion whose computational complexity remains poorly understood, despite the progress achie…
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…
A -Approximation Algorithm for Metric -Median
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee +2
In the classical NP-hard metric -median problem, we are given a set of clients and centers with metric distances between them, along with an integer parameter . The…
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_…
On Approximability of Min-Sum Clustering
Karthik C. S., Euiwoong Lee, Yuval Rabani +2
The min-sum -clustering problem is to partition an input set into clusters to minimize . Although $\ell_2^2…
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…