### Browsing by Department "Institute of Science and Technology Austria"

Now showing 1 - 2 of 2

###### Results Per Page

###### Sort Options

Item Brief Announcement: Temporal Locality in Online Algorithms(Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022-10-01) Pacut, Maciej; Parham, Mahmoud; Rybicki, Joel; Schmid, Stefan; Suomela, Jukka; Tereshchenko, Aleksandr; Technical University of Berlin; University of Vienna; Institute of Science and Technology Austria; Computer Science Professors; Department of Computer Science; Scheideler, ChristianOnline 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.Item Local Mending(Springer, 2022) Balliu, Alkida; Hirvonen, Juho; Melnyk, Darya; Olivetti, Dennis; Rybicki, Joel; Suomela, Jukka; Gran Sasso Science Institute; Department of Computer Science; Institute of Science and Technology Austria; Computer Science Professors; Parter, MeravIn this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log∗n), there is always a restriction Π′⊆ Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.