23 citations · 64 across the 10 of their papers we have counts for
Showing 2012 · cs.DSShow all
3 papers · 2 filters
cs.DS2012
The simplex method is strongly polynomial for deterministic Markov decision processes
Ian Post, Yinyu Ye
We prove that the simplex method with the highest gain/most-negative-reduced cost pivoting rule converges in strongly polynomial time for deterministic Markov decision processes (M…
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…