58 citations · 119 across the 14 of their papers we have counts for
10 papers · 1 filter
Constant Approximation for Individual Preference Stable Clustering
Anders Aamand, Justin Y. Chen, Allen Liu +4
Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is …
Fair Representation Clustering with Several Protected Classes
Zhen Dai, Yury Makarychev, Ali Vakilian
We study the problem of fair -median where each cluster is required to have a fair representation of individuals from different groups. In the fair representation -median pro…
Approximation Algorithms for Socially Fair Clustering
Yury Makarychev, Ali Vakilian
We present an -approximation algorithm for socially fair clustering with the -objective. In this problem, we are given a set of p…
Individual Fairness for -Clustering
Sepideh Mahabadi, Ali Vakilian
We give a local search based algorithm for -median and -means (and more generally for any -clustering with norm cost function) from the perspective of individual…
Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs
Chandra Chekuri, Alina Ene, Ali Vakilian
We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph an…
Sample-Optimal Low-Rank Approximation of Distance Matrices
Piotr Indyk, Ali Vakilian, Tal Wagner +1
A distance matrix represents all pairwise distances, , between two point sets and in an arbit…
Local Computation Algorithms for Spanners
Merav Parter, Ronitt Rubinfeld, Ali Vakilian +1
A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in t…
Set Cover in Sub-linear Time
Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld +2
We study the classic set cover problem from the perspective of sub-linear algorithms. Given access to a collection of sets over elements in the query model, we show that su…
Scalable Fair Clustering
Arturs Backurs, Piotr Indyk, Krzysztof Onak +3
We study the fair variant of the classic -median problem introduced by Chierichetti et al. [2017]. In the standard -median problem, given an input pointset , the goal is t…
Connected Domatic Packings in Node-capacitated Graphs
Alina Ene, Nitish Korula, Ali Vakilian
A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. A dominating set is connected if the subgraph induced by its vertices is…