research
∙
04/14/2023
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
We prove that there is a randomized polynomial-time algorithm that given...
share
research
∙
01/31/2023
Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees
Hierarchical Clustering is a popular unsupervised machine learning metho...
research
∙
01/11/2023
Private estimation algorithms for stochastic block models and mixture models
We introduce general tools for designing efficient private estimation al...
research
∙
12/29/2022
Graph Searching with Predictions
Consider an agent exploring an unknown graph in search of some goal stat...
research
∙
12/13/2022
Streaming Euclidean MST to a Constant Factor
We study streaming algorithms for the fundamental geometric problem of c...
research
∙
11/15/2022
Improved Coresets for Euclidean k-Means
Given a set of n points in d dimensions, the Euclidean k-means problem (...
research
∙
09/05/2022
The Power of Uniform Sampling for Coresets
Motivated by practical generalizations of the classic k-median and k-mea...
research
∙
08/30/2022
On the Fixed-Parameter Tractability of Capacitated Clustering
We study the complexity of the classic capacitated k-median and k-means ...
research
∙
08/29/2022
Fitting Metrics and Ultrametrics with Minimum Disagreements
Given x ∈ (ℝ_≥ 0)^[n]2 recording pairwise distances, the METRIC VIOLATIO...
research
∙
07/22/2022
Correlation Clustering with Sherali-Adams
Given a complete graph G = (V, E) where each edge is labeled + or -, the...
research
∙
07/11/2022
Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
The Uncapacitated Facility Location (UFL) problem is one of the most fun...
research
∙
06/17/2022
Scalable Differentially Private Clustering via Hierarchically Separated Trees
We study the private k-median and k-means clustering problem in d dimens...
research
∙
05/24/2022
Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy
Among the various aspects of algorithmic fairness studied in recent year...
research
∙
04/11/2022
Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets
Motivated by data analysis and machine learning applications, we conside...
research
∙
03/03/2022
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
We study several questions related to diversifying search results. We gi...
research
∙
03/02/2022
Near-Optimal Correlation Clustering with Privacy
Correlation clustering is a central problem in unsupervised learning, wi...
research
∙
02/25/2022
Towards Optimal Lower Bounds for k-median and k-means Coresets
Given a set of points in a metric space, the (k,z)-clustering problem co...
research
∙
12/06/2021
On Complexity of 1-Center in Various Metrics
We consider the classic 1-center problem: Given a set P of n points in a...
research
∙
11/21/2021
Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics
K-median and k-means are the two most popular objectives for clustering ...
research
∙
11/11/2021
A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in FPT Time
In the non-uniform sparsest cut problem, we are given a supply graph G a...
research
∙
11/08/2021
An Improved Local Search Algorithm for k-Median
We present a new local-search algorithm for the k-median clustering prob...
research
∙
10/06/2021
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor
We consider the numerical taxonomy problem of fitting a positive distanc...
research
∙
06/15/2021
Correlation Clustering in Constant Many Parallel Rounds
Correlation clustering is a central topic in unsupervised learning, with...
research
∙
06/15/2021
A Linear-Time n^0.4-Approximation for Longest Common Subsequence
We consider the classic problem of computing the Longest Common Subseque...
research
∙
05/31/2021
A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut
The (non-uniform) sparsest cut problem is the following graph-partitioni...
research
∙
04/13/2021
A New Coreset Framework for Clustering
Given a metric space, the (k,z)-clustering problem consists of finding k...
research
∙
12/22/2020
Fast and Accurate k-means++ via Rejection Sampling
k-means++ <cit.> is a widely used clustering algorithm that is easy to i...
research
∙
09/30/2020
On Approximability of Clustering Problems Without Candidate Centers
The k-means objective is arguably the most widely-used cost function for...
research
∙
09/10/2020
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
Understanding the structure of minor-free metrics, namely shortest path ...
research
∙
09/01/2020
On the computational tractability of a geographic clustering problem arising in redistricting
Redistricting is the problem of dividing a state into a number k of regi...
research
∙
08/15/2020
On Efficient Low Distortion Ultrametric Embedding
A classic problem in unsupervised learning and data analysis is to find ...
research
∙
07/05/2020
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
The Sparsest Cut is a fundamental optimization problem that has been ext...
research
∙
09/15/2019
Online k-means Clustering
We study the problem of online clustering where a clustering algorithm h...
research
∙
05/02/2019
Efficient approximation schemes for uniform-cost clustering problems in planar graphs
We consider the k-Median problem on planar graphs: given an edge-weighte...
research
∙
04/28/2019
Tight FPT Approximations for k-Median and k-Means
We investigate the fine-grained complexity of approximating the classica...
research
∙
04/24/2019
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs
We consider the classic Facility Location problem on planar graphs (non-...
research
∙
03/20/2019
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
We prove essentially tight lower bounds, conditionally to the Exponentia...
research
∙
12/21/2018
Lower bounds for text indexing with mismatches and differences
In this paper we study lower bounds for the fundamental problem of text ...
research
∙
12/20/2018
Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics
We consider the classic Facility Location, k-Median, and k-Means problem...
research
∙
12/19/2018
Approximation Schemes for Capacitated Clustering in Doubling Metrics
Motivated by applications in redistricting, we consider the uniform capa...
research
∙
06/21/2018
Instance-Optimality in the Noisy Value-and Comparison-Model --- Accept, Accept, Strong Accept: Which Papers get in?
Motivated by crowdsourced computation, peer-grading, and recommendation ...
research
∙
03/31/2018
Fast Fencing
We consider very natural "fence enclosure" problems studied by Capoyleas...
research
∙
11/03/2017
The Bane of Low-Dimensionality Clustering
In this paper, we give a conditional lower bound of n^Ω(k) on running ti...
research
∙
08/24/2017
A Fast Approximation Scheme for Low-Dimensional k-Means
We consider the popular k-means problem in d-dimensional Euclidean space...
research
∙
04/07/2016