82 citations · 187 across the 27 of their papers we have counts for
4 papers · 1 filter
Better bounds for matchings in the streaming model
Michael Kapralov
In this paper we present improved bounds for approximating maximum matchings in bipartite graphs in the streaming model. First, we consider the question of how well maximum matchin…
Online submodular welfare maximization: Greedy is optimal
Michael Kapralov, Ian Post, Jan Vondrak
We prove that no online algorithm (even randomized, against an oblivious adversary) is better than 1/2-competitive for welfare maximization with coverage valuations, unless $NP = R…
Single pass sparsification in the streaming model with edge deletions
Ashish Goel, Michael Kapralov, Ian Post
In this paper we give a construction of cut sparsifiers of Benczur and Karger in the {\em dynamic} streaming setting in a single pass over the data stream. Previous constructions e…
Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service
Debojyoti Dutta, Michael Kapralov, Ian Post +1
Infrastructure-as-a-Service (IaaS) providers need to offer richer services to be competitive while optimizing their resource usage to keep costs down. Richer service offerings incl…