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

DOI10.1007/978-3-642-17517-6_37zbMATH Open1311.90171OpenAlexW1522772123MaRDI QIDQ3060752FDOQ3060752

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

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

Mathematics Subject Classification ID

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

Cited In (3)

• The simplex method is strongly polynomial for deterministic Markov decision processes
• Approximating the minimum cycle mean
• Improved and generalized upper bounds on the complexity of policy iteration

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)