A strongly polynomial algorithm for controlled queues

DOI10.1287/MOOR.1090.0415MaRDI QIDQ3169077zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Alexander Zadorojniy, Guy Even, Adam Shwartz

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.1090.0415

zbMATH Keywords

constrained Markov decision processcontrolled queueslinear programmingM/M/1 queueMarkov decision processoptimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Queues and service in operations research (90B22) Linear programming (90C05) Markov and semi-Markov decision processes (90C40)

Recommendations

• The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
• The policy iteration algorithm for average reward Markov decision processes with general state space
• Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems
• scientific article; zbMATH DE number 1424150
• General dynamic programming algorithms applied to polling systems

Cited in

(4)

• Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks
• Strong polynomiality of policy iterations for average-cost MDPs modeling replacement and maintenance problems
• On the reduction of total-cost and average-cost MDPs to discounted mdps
• General dynamic programming algorithms applied to polling systems

This page was built for publication: A strongly polynomial algorithm for controlled queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3169077)