EUVIMEDEUVIMED entdecken
Crossref

A Faster Algorithm for Finding Tarski Fixed Points

John Fearnley, Dömötör Pálvölgyi, Rahul Savani

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →