16 citations · 18 across the 3 of their papers we have counts for
7 papers
Robust Algorithms under Adversarial Injections
Paritosh Garg, Sagar Kale, Lars Rohwedder +1
In this paper, we study streaming and online algorithms in the context of randomness in the input. For several problems, a random order of the input sequence---as opposed to the wo…
Fully-Dynamic Coresets
Monika Henzinger, Sagar Kale
With input sizes becoming massive, coresets -- small yet representative summary of the input -- are relevant more than ever. A weighted set that is a subset of the input is a…
How to Solve Fair -Center in Massive Data Models
Ashish Chiplunkar, Sagar Kale, Sivaramakrishnan Natarajan Ramamoorthy
Fueled by massive data, important decision making is being automated with the help of algorithms, therefore, fairness in algorithms has become an especially important research topi…
Beating Greedy for Stochastic Bipartite Matching
Buddhima Gamlath, Sagar Kale, Ola Svensson
We consider the maximum bipartite matching problem in stochastic settings, namely the query-commit and price-of-information models. In the query-commit model, an edge e independent…
Weighted Matchings via Unweighted Augmentations
Buddhima Gamlath, Sagar Kale, Slobodan Mitrović +1
We design a generic method for reducing the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide eff…
Small Space Stream Summary for Matroid Center
Sagar Kale
In the matroid center problem, which generalizes the -center problem, we need to pick a set of centers that is an independent set of a matroid with rank . We study this probl…