research
∙
08/20/2023
Higher-Order Cheeger Inequality for Partitioning with Buffers
We prove a new generalization of the higher-order Cheeger inequality for...
share
research
∙
08/16/2023
Approximation Algorithms for Norm Multiway Cut
We consider variants of the classic Multiway Cut problem. Multiway Cut a...
research
∙
05/23/2023
Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
We show that a simple single-pass semi-streaming variant of the Pivot al...
research
∙
04/18/2023
Random Cuts are Optimal for Explainable k-Medians
We show that the RandomCoordinateCut algorithm gives the optimal competi...
research
∙
12/24/2022
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant
We study the natural problem of Triplet Reconstruction (also Rooted Trip...
research
∙
11/04/2021
Explainable k-means. Don't be greedy, plant bigger trees!
We provide a new bi-criteria Õ(log^2 k) competitive algorithm for explai...
research
∙
08/11/2021
Local Correlation Clustering with Asymmetric Classification Errors
In the Correlation Clustering problem, we are given a complete weighted ...
research
∙
08/11/2021
Correlation Clustering with Asymmetric Classification Errors
In the Correlation Clustering problem, we are given a weighted graph G w...
research
∙
07/02/2021
Near-optimal Algorithms for Explainable k-Medians and k-Means
We consider the problem of explainable k-medians and k-means introduced ...
research
∙
11/30/2020
Batch Optimization for DNA Synthesis
Large pools of synthetic DNA molecules have been recently used to reliab...
research
∙
10/27/2020
Improved Guarantees for k-means++ and k-means++ Parallel
In this paper, we study k-means++ and k-means++ parallel, the two most p...
research
∙
12/15/2019
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Hierarchical Clustering is an unsupervised data analysis method which ha...
research
∙
02/27/2019
Improved algorithms for Correlation Clustering with local objectives
Correlation Clustering is a powerful graph partitioning model that aims ...
research
∙
11/08/2018
Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions
We introduce and study the notion of an outer bi-Lipschitz extension of ...
research
∙
11/08/2018