82 citations · 187 across the 27 of their papers we have counts for
Showing 2012 · cs.DSShow all
3 papers · 2 filters
cs.DS2012
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…
cs.DS2012
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…
cs.DS2012★ 23 cited
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…