32 citations · 63 across the 14 of their papers we have counts for
14 papers · 1 filter
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…
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…
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…
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…
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…
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee +1
The Uncapacitated Facility Location (UFL) problem is one of the most fundamental clustering problems: Given a set of clients and a set of facilities in a metric space $(C \…
Scalable Differentially Private Clustering via Hierarchically Separated Trees
Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi +5
We study the private -median and -means clustering problem in dimensional Euclidean space. By leveraging tree embeddings, we give an efficient and easy to implement algor…
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…
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…
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…
Efficient Similarity Search in Dynamic Data Streams
Marc Bury, Chris Schwiegelshohn, Mara Sorella
The Jaccard index is an important similarity measure for item sets and Boolean data. On large datasets, an exact similarity computation is often infeasible for all item pairs both…
Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
Marc Bury, Chris Schwiegelshohn
This paper presents an algorithm for estimating the weight of a maximum weighted matching by augmenting any estimation routine for the size of an unweighted matching. The algorithm…
Random Projections for k-Means: Maintaining Coresets Beyond Merge & Reduce
Marc Bury, Chris Schwiegelshohn
We give a new construction for a small space summary satisfying the coreset guarantee of a data set with respect to the -means objective function. The number of points required…