# Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths

Preprint · Adam Karczmarz

- Archive id: arxiv:2110.15070
- Published: 2021-10-28
- arXiv: https://arxiv.org/abs/2110.15070
- Source URL: https://arxiv.org/abs/2110.15070
- PDF: https://arxiv.org/pdf/2110.15070
- Provenance: arxiv

## Abstract

We revisit the problem of finding optimal strategies for deterministic Markov Decision Processes (DMDPs), and a closely related problem of testing feasibility of systems of $m$ linear inequalities on $n$ real variables with at most two variables per inequality (2VPI). We give a randomized trade-off algorithm solving both problems and running in $\\tilde{O}(nmh+(n/h)^3)$ time using $\\tilde{O}(n^2/h+m)$ space for any parameter $h\\in \[1,n\]$. In particular, using subquadratic space we get $\\tilde{O}(nm+n^{3/2}m^{3/4})$ running time, which improves by a polynomial factor upon all the known upper bounds for non-dense instances with $m=O(n^{2-ε})$. Moreover, using linear space we match the randomized $\\tilde{O}(nm+n^3)$ time bound of Cohen and Megiddo \[SICOMP'94\] that required $\\tildeΘ(n^2+m)$ space. Additionally, we show a new algorithm for the Discounted All-Pairs Shortest Paths problem, introduced by Madani et al. \[TALG'10\], that extends the DMDPs with optional end vertices. For the case of uniform discount factors, we give a deterministic algorithm running in $\\tilde{O}(n^{3/2}m^{3/4})$ time, which improves significantly upon the randomized bound $\\tilde{O}(n^2\\sqrt{m})$ of Madani et al.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.