Brief Announcement: Temporal Locality in Online Algorithms

Maciej Pacut*, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela, Aleksandr Tereshchenko

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientific

39 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
Otsikko36th International Symposium on Distributed Computing, DISC 2022
ToimittajatChristian Scheideler
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivumäärä3
ISBN (elektroninen)978-3-95977-255-6
DOI - pysyväislinkit
TilaJulkaistu - 1 lokak. 2022
OKM-julkaisutyyppiB3 Vertaisarvioimaton artikkeli konferenssijulkaisussa
TapahtumaInternational Symposium on Distributed Computing - Augusta, Yhdysvallat
Kesto: 25 lokak. 202227 lokak. 2022
Konferenssinumero: 36

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
KustantajaSchloss Dagstuhl-Leibniz-Zentrum für Informatik
Vuosikerta246
ISSN (painettu)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
LyhennettäDISC
Maa/AlueYhdysvallat
KaupunkiAugusta
Ajanjakso25/10/202227/10/2022

Sormenjälki

Sukella tutkimusaiheisiin 'Brief Announcement: Temporal Locality in Online Algorithms'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä