University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Guest Talks


A Strongly Polynomial Algorithm for Controlled Queues


Prof. Guy Even, Tel Aviv University
Tel Aviv, Israel

date & place

Tuesday, 11.08.2009, 14:15 h
Room C252


We consider the problem of computing optimal policies of finite-state, finite-action Markov Decision Processes (MDPs). We present a simplex-like algorithm with a new pivot rule. In the general case this path might be exponentially long in number of states and actions. We prove that the number of pivots is polynomial if the MDP satisfies a special property that we call the coupling property. Thus we obtain a strongly polynomial algorithm for MDPs that satisfy the coupling property.

We prove that discrete time versions of controlled M/M/1 queues induce MDPs that satisfy the coupling property. The only previously known polynomial algorithm for controlled M/M/1 queues in the expected average cost model is based on linear programming (and is not known to be strongly polynomial). Our algorithm works both for the discounted and expected average cost models, and the running time does not depend on the discount factor.