Talk by Peter Bro Miltersen at DTU on February 2 -- your time preference?
Valentin Goranko
Dear algolog-icians,
(apologies if you receive this in duplicate -- I am not sure if one mailing list subsumes the other.)
Peter Bro Miltersen from Aarhus University will be visiting DTU on Feb 2 on the occasion of the thesis defence of my master student, and has kindly agreed to give a talk at IMM, too --see details below.
He prefers to complete both tasks within the period 11-18h, so we can schedule the defence in the morning (from 11am) and the talk in the afternoon (say, from 2pm) or the other way around.
If interested in attending the talk, please send me your preferences asap, but not later than this Friday, so I can do the best poissible scheduling.
med venlig hilsen fra Johannesburg,
Val
Recent results on Howard's algorithm
Peter Bro Miltersen, Aarhus University
Howard's algoritme (a.k.a. policy iteration) is a standard algorithm for
solving Markov decision processes. Furthermore, generalizations of the
algorithm solve various kinds of two-player games, including parity
games, concurrent reachability games and Shapley's stochastic games. The
worst case time complexity of the algorithm was until recently poorly
understood, but in recent years, a surge of publications on the topic
have given us an almost complete understanding of its complexity in the
various settings in which it applies. We shall give a survey of these
results and also explain how they unexpectedly led to the answer to a
classical open question concerning the complexity of a randomized
variant of the simplex algorithm for linear programming.
Valentin Goranko
Based on the responses I received, the best starting time I can choose for the talk is 14.30. The venue will be 322/033.
An official announcement will follow soon.
Mvh,
Val