Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Lower Bounds for Howard’s Algorithm for Finding Minimum Mean-Cost Cycles
verfasst von : Thomas Dueholm Hansen, Uri Zwick
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Howard’s policy iteration algorithm is one of the most widely used algorithms for finding optimal policies for controlling
Markov Decision Processes
(MDPs). When applied to weighted directed graphs, which may be viewed as
Deterministic
MDPs (DMDPs), Howard’s algorithm can be used to find Minimum Mean-Cost cycles (MMCC). Experimental studies suggest that Howard’s algorithm works extremely well in this context. The theoretical complexity of Howard’s algorithm for finding MMCCs is a mystery. No polynomial time bound is known on its running time. Prior to this work, there were only linear lower bounds on the number of iterations performed by Howard’s algorithm. We provide the first weighted graphs on which Howard’s algorithm performs Ω(
n
2
) iterations, where
n
is the number of vertices in the graph.