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

zbMATH Open1423.05181MaRDI QIDQ4633909FDOQ4633909

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

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

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)

Cited In (3)

• Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles
• On the complexity of shortest path problems on discounted cost graphs
• 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)