Faster algorithms for Markov decision processes with low treewidth

K. Chatterjee, J. Ła̧Cki, 8044 (2013) 543–558.


Conference Paper | Published | English
Author
Department
Series Title
LNCS
Abstract
We consider two core algorithmic problems for probabilistic verification: the maximal end-component decomposition and the almost-sure reachability set computation for Markov decision processes (MDPs). For MDPs with treewidth k, we present two improved static algorithms for both the problems that run in time O(n·k 2.38·2k ) and O(m·logn· k), respectively, where n is the number of states and m is the number of edges, significantly improving the previous known O(n·k·√n· k) bound for low treewidth. We also present decremental algorithms for both problems for MDPs with constant treewidth that run in amortized logarithmic time, which is a huge improvement over the previously known algorithms that require amortized linear time.
Publishing Year
Date Published
2013-07-01
Volume
8044
Page
543 - 558
Conference
CAV: Computer Aided Verification
Conference Location
St. Petersburg, Russia
Conference Date
2013-07-13 – 2013-07-19
IST-REx-ID

Cite this

Chatterjee K, Ła̧Cki J. Faster algorithms for Markov decision processes with low treewidth. 2013;8044:543-558. doi:10.1007/978-3-642-39799-8_36
Chatterjee, K., & Ła̧Cki, J. (2013). Faster algorithms for Markov decision processes with low treewidth. Presented at the CAV: Computer Aided Verification, St. Petersburg, Russia: Springer. https://doi.org/10.1007/978-3-642-39799-8_36
Chatterjee, Krishnendu, and Jakub Ła̧Cki. “Faster Algorithms for Markov Decision Processes with Low Treewidth.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-39799-8_36.
K. Chatterjee and J. Ła̧Cki, “Faster algorithms for Markov decision processes with low treewidth,” vol. 8044. Springer, pp. 543–558, 2013.
Chatterjee K, Ła̧Cki J. 2013. Faster algorithms for Markov decision processes with low treewidth. 8044, 543–558.
Chatterjee, Krishnendu, and Jakub Ła̧Cki. Faster Algorithms for Markov Decision Processes with Low Treewidth. Vol. 8044, Springer, 2013, pp. 543–58, doi:10.1007/978-3-642-39799-8_36.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1304.0084

Search this title in

Google Scholar