Brief Announcement: Temporal Locality in Online Algorithms
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2022-10-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
3
Series
36th International Symposium on Distributed Computing, DISC 2022, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 246
Abstract
Online algorithms make decisions based on past inputs, with the goal of being competitive against an algorithm that sees also future inputs. In this work, we introduce time-local online algorithms; these are online algorithms in which the output at any given time is a function of only T latest inputs. Our main observation is that time-local online algorithms are closely connected to local distributed graph algorithms: distributed algorithms make decisions based on the local information in the spatial dimension, while time-local online algorithms make decisions based on the local information in the temporal dimension. We formalize this connection, and show how we can directly use the tools developed to study distributed approximability of graph optimization problems to prove upper and lower bounds on the competitive ratio achieved with time-local online algorithms. Moreover, we show how to use computational techniques to synthesize optimal time-local algorithms.Description
Funding Information: Funding This research has received funding from the German Research Foundation (DFG), grant 470029389 (FlexNets), 2021-2024, and the Marie Skłodowska-Curie grant agreement No. 840605. Publisher Copyright: © Maciej Pacut, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, and Aleksandr Tereshchenko.
Keywords
distributed algorithms, Online algorithms
Other note
Citation
Pacut, M, Parham, M, Rybicki, J, Schmid, S, Suomela, J & Tereshchenko, A 2022, Brief Announcement: Temporal Locality in Online Algorithms . in C Scheideler (ed.), 36th International Symposium on Distributed Computing, DISC 2022 ., 52, Leibniz International Proceedings in Informatics, LIPIcs, vol. 246, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, Augusta, Georgia, United States, 25/10/2022 . https://doi.org/10.4230/LIPIcs.DISC.2022.52