58 citations · 119 across the 14 of their papers we have counts for
15 papers
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 …
Approximation Algorithms for Fair Range Clustering
Sèdjro S. Hotegni, Sepideh Mahabadi, Ali Vakilian
This paper studies the fair range clustering problem in which the data points are from different demographic groups and the goal is to pick centers with the minimum clustering…
Sequential Strategic Screening
Lee Cohen, Saeed Sharifi-Malvajerdi, Kevin Stangl +2
We initiate the study of strategic behavior in screening processes with multiple classifiers. We focus on two contrasting settings: a conjunctive setting in which an individual mus…
Individual Preference Stability for Clustering
Saba Ahmadi, Pranjal Awasthi, Samir Khuller +4
In this paper, we propose a natural notion of individual preference (IP) stability for clustering, which asks that every data point, on average, is closer to the points in its own…
Multi Stage Screening: Enforcing Fairness and Maximizing Efficiency in a Pre-Existing Pipeline
Avrim Blum, Kevin Stangl, Ali Vakilian
Consider an actor making selection decisions using a series of classifiers, which we term a sequential screening process. The early stages filter out some applicants, and in the fi…
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…
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster +5
We develop a new framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a sce…
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…