23 citations · 64 across the 10 of their papers we have counts for
10 papers
Combinatorial Algorithms for Rooted Prize-Collecting Walks and Applications to Orienteering and Minimum-Latency Problems
Sina Dezfuli, Zachary Friggstad, Ian Post +1
We consider the rooted prize-collecting walks (PCW) problem, wherein we seek a collection of rooted walks having minimum prize-collecting cost, which is the (total cost of walk…
A -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann +1
Graphs with bounded highway dimension were introduced by Abraham et al. [SODA 2010] as a model of transportation networks. We show that any such graph can be embedded into a distri…
Linear-Programming based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems
Ian Post, Chaitanya Swamy
We consider various {\em multi-vehicle versions of the minimum latency problem}. There is a fleet of vehicles located at one or more depot nodes, and we seek a collection of ro…
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…