128 citations · 139 across the 20 of their papers we have counts for
5 papers · 2 filters
An Improved Subquadratic Bound for Online Bisection
Marcin Bienkowski, Stefan Schmid
The online bisection problem is a natural dynamic variant of the classic bisection problem, where one has to dynamically maintain a partition of elements into two clusters of c…
Polylog-Competitive Algorithms for Dynamic Balanced Graph Partitioning for Ring Demands
Harald Räcke, Stefan Schmid, Ruslan Zabrodin
The performance of many large-scale and data-intensive distributed systems critically depends on the capacity of the interconnecting network. This paper is motivated by the vision…
Online Algorithms with Randomly Infused Advice
Yuval Emek, Yuval Gil, Maciej Pacut +1
We introduce a novel method for the rigorous quantitative evaluation of online algorithms that relaxes the "radical worst-case" perspective of classic competitive analysis. In cont…
SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree
Arash Pourdamghani, Chen Avin, Robert Sama +1
We consider the fundamental problem of designing a self-adjusting tree, which efficiently and locally adapts itself towards the demand it serves (namely accesses to the items store…
Dynamic Maintenance of Monotone Dynamic Programs and Applications
Monika Henzinger, Stefan Neumann, Harald Räcke +1
Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays…