Thomas Dueholm Hansen
Postdoc at the Department of
Computer Science, Tel Aviv 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:
Improved upper bounds for Random-Edge and Random-Jump on
abstract cubes
Thomas Dueholm Hansen,
Mike Paterson and
Uri Zwick
Manuscript, online.
The complexity of interior point methods for solving
discounted turn-based stochastic games
Thomas Dueholm Hansen and
Rasmus Ibsen-Jensen
Manuscript, online.
A faster algorithm for solving one-clock priced timed games
Thomas Dueholm Hansen,
Rasmus Ibsen-Jensen and
Peter Bro Miltersen
Manuscript, 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).
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).