Lower bounds for Howard's algorithm for finding minimum mean-cost cycles

DOI10.1007/978-3-642-17517-6_37MaRDI QIDQ3060752zbMATH OpenOpenAlexFDO

Authors Thomas Dueholm Hansen, Uri Zwick

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17517-6_37

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Markov and semi-Markov decision processes (90C40) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Algorithms for finding the minimum cycle mean in the weighted directed graph
• A polynomial time bound for Howard's policy improvement algorithm
• Approximating the minimum cycle mean
• scientific article; zbMATH DE number 3961380
• Maximum cycle-means of weighted digraphs

Cited in

(4)

• Approximating the minimum cycle mean
• Improved and generalized upper bounds on the complexity of policy iteration
• The simplex method is strongly polynomial for deterministic Markov decision processes
• Smoothed analysis of deterministic discounted and Mean-payoff games

This page was built for publication: Lower bounds for Howard's algorithm for finding minimum mean-cost cycles

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