Discounted deterministic Markov decision processes and discounted all-pairs shortest paths

MaRDI QIDQ4633909zbMATH OpenFDO

Authors Omid Madani, Mikkel Thorup, Uri Zwick

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496874

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Paths and cycles (05C38) Markov and semi-Markov decision processes (90C40)

Recommendations

• Discounted deterministic Markov decision processes and discounted all-pairs shortest paths
• Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles
• The simplex method is strongly polynomial for deterministic Markov decision processes
• On the complexity of shortest path problems on discounted cost graphs

Cited in

(3)

• On the complexity of shortest path problems on discounted cost graphs
• Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles
• Discounted deterministic Markov decision processes and discounted all-pairs shortest paths

This page was built for publication: Discounted deterministic Markov decision processes and discounted all-pairs shortest paths

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