Brief Announcement: Temporal Locality in Online Algorithms

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientific

5 Downloads (Pure)

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.

Original languageEnglish
Title of host publication36th International Symposium on Distributed Computing, DISC 2022
EditorsChristian Scheideler
PublisherSchloss Dagstuhl-Leibniz-Zentrum für Informatik
Number of pages3
ISBN (Electronic)9783959772556
DOIs
Publication statusPublished - 1 Oct 2022
MoE publication typeB3 Non-refereed article in conference proceedings
EventInternational Symposium on Distributed Computing - Augusta, United States
Duration: 25 Oct 202227 Oct 2022
Conference number: 36

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl-Leibniz-Zentrum für Informatik
Volume246
ISSN (Print)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
Country/TerritoryUnited States
CityAugusta
Period25/10/202227/10/2022

Keywords

  • distributed algorithms
  • Online algorithms

Fingerprint

Dive into the research topics of 'Brief Announcement: Temporal Locality in Online Algorithms'. Together they form a unique fingerprint.

Cite this