13 citations · 20 across the 3 of their papers we have counts for
3 papers
Errata for: A subexponential lower bound for the Random Facet algorithm for Parity Games
Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick
In Friedmann, Hansen, and Zwick (2011) we claimed that the expected number of pivoting steps performed by the Random-Facet algorithm of Kalai and of Matousek, Sharir, and Welzl is…
Random-Facet and Random-Bland require subexponential time even for shortest paths
Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick
The Random-Facet algorithm of Kalai and of Matousek, Sharir and Welzl is an elegant randomized algorithm for solving linear programs and more general LP-type problems. Its expected…
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick
Ye showed recently that the simplex method with Dantzig pivoting rule, as well as Howard's policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a con…