23 citations · 64 across the 10 of their papers we have counts for
4 papers · 1 filter
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…
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…