19 citations · 27 across the 17 of their papers we have counts for
21 papers · 1 filter
A Configuration-LP Framework for Connected -Median Clustering
Kushagra Chatterjee, Rojin Rezvan, Ali Vakilian
We study the \emph{connected -median} clustering problem, a clustering problem that augments the classical -median objective with connectivity constraints. We focus on the \e…
An Optimal Algorithm for Stochastic Vertex Cover
Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju +5
The goal in the stochastic vertex cover problem is to obtain an approximately minimum vertex cover for a graph that is realized by sampling each edge independently with s…
Sublinear Metric Steiner Forest via Maximal Independent Set
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski +1
In this work we consider the Metric Steiner Forest problem in the sublinear time model. Given a set of points in a metric space where distances are provided by means of que…
Max-Cut with Multiple Cardinality Constraints
Yury Makarychev, Madhusudhan Reddy Pittu, Ali Vakilian
We study the classic Max-Cut problem under multiple cardinality constraints, which we refer to as the Constrained Max-Cut problem. Given a graph , a partition of the vert…
Guessing Efficiently for Constrained Subspace Approximation
Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu +2
In this paper we study constrained subspace approximation problem. Given a set of points in , the goal of the {\em subspace approximation} pr…
Streaming Algorithms for Network Design
Chandra Chekuri, Rhea Jain, Sepideh Mahabadi +1
We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph and an integer…