pipette
ENEnglish

A Quasipolynomial Algorithm for Contractions

Ashkan Soleymani, Gabriele Farina

Preprint

En palabras de los autores

We give an algorithm for computing an -approximate fixed point of any -dimensional nonexpansion with respect to the norm in time . 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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.