research
∙
07/15/2023
Fully Scalable MPC Algorithms for Clustering in High Dimension
We design new algorithms for k-clustering in high-dimensional Euclidean ...
share
research
∙
06/05/2023
Near-Optimal Quantum Coreset Construction Algorithms for Clustering
k-Clustering in ℝ^d (e.g., k-median and k-means) is a fundamental machin...
research
∙
04/04/2023
Algorithms for the Generalized Poset Sorting Problem
We consider a generalized poset sorting problem (GPS), in which we are g...
research
∙
02/22/2023
The Power of Uniform Sampling for k-Median
We study the power of uniform sampling for k-Median in various metric sp...
research
∙
01/20/2023
Coresets for Clustering with General Assignment Constraints
Designing small-sized coresets, which approximately preserve the costs o...
research
∙
11/10/2022
Streaming Euclidean Max-Cut: Dimension vs Data Reduction
Max-Cut is a fundamental problem that has been studied extensively in va...
research
∙
10/19/2022
Near-optimal Coresets for Robust Clustering
We consider robust clustering problems in ℝ^d, specifically k-clustering...
research
∙
10/01/2022
On The Relative Error of Random Fourier Features for Preserving Kernel Distance
The method of random Fourier features (RFF), proposed in a seminal paper...
research
∙
09/05/2022
The Power of Uniform Sampling for Coresets
Motivated by practical generalizations of the classic k-median and k-mea...
research
∙
04/05/2022
Streaming Facility Location in High Dimension via New Geometric Hashing
In Euclidean Uniform Facility Location, the input is a set of clients in...
research
∙
10/17/2021
Online Facility Location with Predictions
We provide nearly optimal algorithms for online facility location (OFL) ...
research
∙
10/06/2021
Coresets for Kernel Clustering
We devise the first coreset for kernel k-Means, and use it to obtain new...
research
∙
06/30/2021
Coresets for Clustering with Missing Values
We provide the first coreset for clustering points in ℝ^d that have mult...
research
∙
11/09/2020
Streaming Algorithms for Geometric Steiner Forest
We consider a natural generalization of the Steiner tree problem, the St...
research
∙
04/16/2020
Coresets for Clustering in Excluded-minor Graphs and Beyond
Coresets are modern data-reduction tools that are widely used in data an...
research
∙
07/10/2019
Coresets for Clustering in Graphs of Bounded Treewidth
We initiate the study of coresets for clustering in graph metrics, i.e.,...
research
∙
06/20/2019
Coresets for Clustering with Fairness Constraints
In a recent work, Chierichetti et al. studied the following "fair" varia...
research
∙
03/11/2019
Coresets for Ordered Weighted Clustering
We design coresets for Ordered k-Median, a generalization of classical c...
research
∙
04/07/2018