Thomas Dueholm Hansen



Postdoc at the Department of Management Science and Engineering, Stanford University.

Email: tdh @ cs.au.dk

I was lecturing on the simplex algorithm and the Hirsch conjecture at the MADALGO & CTIC Summer School on High-dimensional Geometric Computing: Lecture 1, Lecture 2, Lecture 3.

My dissertation is available here.

List of publications:

Random-Facet and Random-Bland require subexponential time even for shortest paths
Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick
Manuscript, online.

Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles
Thomas Dueholm Hansen, Haim Kaplan, and Uri Zwick
Manuscript (to appear at SODA'14), online.

Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
Thomas Dueholm Hansen, Mike Paterson, and Uri Zwick
Manuscript (to appear at SODA'14), online.

A faster algorithm for solving one-clock priced timed games
Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, and Peter Bro Miltersen
CONCUR'13, online.

The complexity of interior point methods for solving discounted turn-based stochastic games
Thomas Dueholm Hansen and Rasmus Ibsen-Jensen
CiE'13, online.

Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick
Journal of the ACM, 60(1):1-16, 2013, online (Slides).

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick
STOC'11, co-winner of the Best Paper Award, online (Older version with full proofs, slides).

A subexponential lower bound for the Random Facet algorithm for Parity Games
Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick
SODA'11, online (Slides) [Errata].

Lower bounds for Howard's algorithm for finding Minimum Mean-Cost Cycles
Thomas Dueholm Hansen and Uri Zwick
ISAAC'10, online (Slides).

On Acyclicity of Games with Cycles
Daniel Andersson, Vladimir Gurvich, and Thomas Dueholm Hansen
Discrete Applied Mathematics, 158(10):1049-1063, 2010, online (Slides).

Improved Bounds for Facility Location Games with Fair Cost Allocation
Thomas Dueholm Hansen and Orestis A. Telelis
COCOA'09, online.

Approximability and Parameterized Complexity of Minmax Values
Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen
WINE'08, online.

On Pure and (approximate) Strong Equilibria of Facility Location Games
Thomas Dueholm Hansen and Orestis A. Telelis
WINE'08, online (Slides).

On Range of Skill
Thomas Dueholm Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen
AAAI'08, online (Slides).