Quasipolynomial algorithm finds approximate fixed points of ℓ∞ contractions
Original title: A Quasipolynomial Algorithm for $\ell_\infty$ Contractions
The method geometrically shrinks the search region and implies simple stochastic games can be solved in quasipolynomial time.
The paper gives an algorithm that computes an ε-approximate fixed point of any d-dimensional nonexpansion under the ℓ∞ norm in time log(1/ε) to the power O(log² d). The method uses a boosting argument to shrink the search region geometrically. As a consequence, simple stochastic games can be solved in quasipolynomial time.
- Runtime is log(1/ε) raised to O(log squared d).
- The core technique is a boosting argument that shrinks the search region.
- Simple stochastic games are solvable in quasipolynomial time as a consequence.
From the original article
1 min read at arxiv.orgWe give an algorithm for computing an $\eps$-approximate fixed point of any $d$-dimensional nonexpansion with respect to the $\ell_\infty$ norm in time $\log(1/\eps)^{O(\log^2 d)}$. At its core, our method uses a boosting argument to geometrically shrink a search region. Among other consequences, our algorithm implies that simple stochastic games can be solved in quasipolynomial time.
By Ashkan Soleymani · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.