Computing a Fixed Point of Contraction Maps in Polynomial Queries
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916888601165824 |
|---|---|
| author | Chen, Xi Li, Yuhao Yannakakis, Mihalis |
| author_facet | Chen, Xi Li, Yuhao Yannakakis, Mihalis |
| contents | We give an algorithm for finding an $ε$-fixed point of a contraction map $f:[0,1]^k\mapsto[0,1]^k$ under the $\ell_\infty$-norm with query complexity $O (k\log (1/ε) )$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_19911 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing a Fixed Point of Contraction Maps in Polynomial Queries Chen, Xi Li, Yuhao Yannakakis, Mihalis Computational Complexity Data Structures and Algorithms Computer Science and Game Theory We give an algorithm for finding an $ε$-fixed point of a contraction map $f:[0,1]^k\mapsto[0,1]^k$ under the $\ell_\infty$-norm with query complexity $O (k\log (1/ε) )$. |
| title | Computing a Fixed Point of Contraction Maps in Polynomial Queries |
| topic | Computational Complexity Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2403.19911 |