58 citations · 119 across the 14 of their papers we have counts for
5 papers · 1 filter
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…