4 papers
Semi-Streaming Algorithms for Submodular Matroid Intersection
Paritosh Garg, Linus Jordan, Ola Svensson
While the basic greedy algorithm gives a semi-streaming algorithm with an approximation guarantee of for the \emph{unweighted} matching problem, it was only recently that Paz a…
The Submodular Santa Claus Problem in the Restricted Assignment Case
Etienne Bamas, Paritosh Garg, Lars Rohwedder
The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned…
The Combinatorial Santa Claus Problem or: How to Find Good Matchings in Non-Uniform Hypergraphs
Etienne Bamas, Paritosh Garg, Lars Rohwedder
We consider hypergraphs on vertices where each hyperedge contains exactly one vertex in . Our goal is to select a matching that covers all of , but we allow each se…
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…