A Faster Algorithm for Finding Tarski Fixed Points
ACM Transactions on Algorithms · 31.07.2022 · 18 (3) · 1-23
DOI: 10.1145/3524044 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 11.10.2022. Verfasst von John Fearnley und 2 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 14 Literaturangaben.
Abstract (Originalsprache)
Dang et al. have given an algorithm that can find a Tarski fixed point in a k -dimensional lattice of width n using O (log k n ) queries [ 2 ]. Multiple authors have conjectured that this algorithm is optimal [ 2 , 7 ], and indeed this has been proven for two-dimensional instances [ 7 ]. We show that these conjectures are false in dimension three or higher by giving an O (log 2 n ) query algorithm for the three-dimensional Tarski problem. We also give a new decomposition theorem for k -dimensional Tarski problems which, in combination with our new algorithm for three dimensions, gives an O (log 2 ⌈k/3⌉ n ) query algorithm for the k -dimensional problem.
Zitieren
APA
Fearnley, J., Pálvölgyi, D., & Savani, R. (2022). A Faster Algorithm for Finding Tarski Fixed Points. ACM Transactions on Algorithms, 18(3), 1-23. https://doi.org/10.1145/3524044
Vancouver
Fearnley J, Pálvölgyi D, Savani R. A Faster Algorithm for Finding Tarski Fixed Points. ACM Transactions on Algorithms. 2022;18(3):1-23. doi:10.1145/3524044
BibTeX
@article{Fearnley2022,
author = {Fearnley, John and Pálvölgyi, Dömötör and Savani, Rahul},
title = {A Faster Algorithm for Finding Tarski Fixed Points},
journal = {ACM Transactions on Algorithms},
year = {2022},
volume = {18},
number = {3},
pages = {1--23},
doi = {10.1145/3524044}
}
EUVIMED