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
∙
02/01/2023
Approximating Red-Blue Set Cover
We provide a new approximation algorithm for the Red-Blue Set Cover prob...
research
∙
06/15/2022
Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes
We give efficient deterministic one-pass streaming algorithms for findin...
research
∙
02/03/2022
Fair Representation Clustering with Several Protected Classes
We study the problem of fair k-median where each cluster is required to ...
research
∙
11/08/2021
Approximating Fair Clustering with Cascaded Norm Objectives
We introduce the (p,q)-Fair Clustering problem. In this problem, we are ...
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
∙
03/03/2021
Approximation Algorithms for Socially Fair Clustering
We present an (e^O(p)logℓ/loglogℓ)-approximation algorithm for socially ...
research
∙
05/28/2019
Regression via Kirszbraun Extension with Applications to Imitation Learning
Learning by demonstration is a versatile and rapid mechanism for transfe...
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
Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
Consider an instance of Euclidean k-means or k-medians clustering. We sh...
research
∙
11/29/2013