research
∙
06/11/2023
Approximation Algorithms for Fair Range Clustering
This paper studies the fair range clustering problem in which the data p...
share
research
∙
06/11/2023
Learning the Positions in CountSketch
We consider sketching algorithms which first compress data by multiplica...
research
∙
02/01/2023
Approximating Red-Blue Set Cover
We provide a new approximation algorithm for the Red-Blue Set Cover prob...
research
∙
07/07/2022
Individual Preference Stability for Clustering
In this paper, we propose a natural notion of individual preference (IP)...
research
∙
04/26/2022
Faster Fundamental Graph Algorithms via Learned Predictions
We consider the question of speeding up classic graph algorithms with ma...
research
∙
03/14/2022
Multi Stage Screening: Enforcing Fairness and Maximizing Efficiency in a Pre-Existing Pipeline
Consider an actor making selection decisions using a series of classifie...
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
∙
06/26/2021
Improved Approximation Algorithms for Individually Fair Clustering
We consider the k-clustering problem with ℓ_p-norm cost, which includes ...
research
∙
03/03/2021
Approximation Algorithms for Socially Fair Clustering
We present an (e^O(p)logℓ/loglogℓ)-approximation algorithm for socially ...
research
∙
07/20/2020
On Learned Sketches for Randomized Numerical Linear Algebra
We study "learning-based" sketching approaches for diverse tasks in nume...
research
∙
02/17/2020
(Individual) Fairness for k-Clustering
We give a local search based algorithm for k-median (k-means) clustering...
research
∙
10/30/2019
Improved Local Computation Algorithm for Set Cover via Sparsification
We design a Local Computation Algorithm (LCA) for the set cover problem....
research
∙
10/30/2019
Learning-Based Low-Rank Approximations
We introduce a "learning-based" algorithm for the low-rank decomposition...
research
∙
10/16/2019
Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs
We consider node-weighted survivable network design (SNDP) in planar gra...
research
∙
08/14/2019
(Learned) Frequency Estimation Algorithms under Zipfian Distribution
The frequencies of the elements in a data stream are an important statis...
research
∙
06/02/2019
Sample-Optimal Low-Rank Approximation of Distance Matrices
A distance matrix A ∈ R^n × m represents all pairwise distances, A_ij=d(...
research
∙
02/21/2019
Local Computation Algorithms for Spanners
A graph spanner is a fundamental graph structure that faithfully preserv...
research
∙
02/10/2019
Set Cover in Sub-linear Time
We study the classic set cover problem from the perspective of sub-linea...
research
∙
02/10/2019
Scalable Fair Clustering
We study the fair variant of the classic k-median problem introduced by ...
research
∙
06/07/2018