The simplex method is strongly polynomial for deterministic Markov decision processes

DOI10.1137/1.9781611973105.105zbMath1423.90138OpenAlexW2949647541MaRDI QIDQ5741814

Yinyu Ye, Ian Post

Publication date: 15 May 2019

Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973105.105

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Markov and semi-Markov decision processes (90C40)

Related Items (2)

A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations ⋮ Towards solving 2-TBSG efficiently

This page was built for publication: The simplex method is strongly polynomial for deterministic Markov decision processes