6 citations · 15 across the 7 of their papers we have counts for
5 papers · 1 filter
Tight Bounds for Online Graph Partitioning
Monika Henzinger, Stefan Neumann, Harald Räcke +1
We consider the following online optimization problem. We are given a graph and each vertex of the graph is assigned to one of servers, where servers have capacity a…
Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity
Monika Henzinger, Stefan Neumann, Andreas Wiese
Graph coloring is a fundamental problem in computer science. We study the fully dynamic version of the problem in which the graph is undergoing edge insertions and deletions and we…
Efficient Distributed Workload (Re-)Embedding
Monika Henzinger, Stefan Neumann, Stefan Schmid
Modern networked systems are increasingly reconfigurable, enabling demand-aware infrastructures whose resources can be adjusted according to the workload they currently serve. Such…
New Amortized Cell-Probe Lower Bounds for Dynamic Problems
Sayan Bhattacharya, Monika Henzinger, Stefan Neumann
We build upon the recent papers by Weinstein and Yu (FOCS'16), Larsen (FOCS'12), and Clifford et al. (FOCS'15) to present a general framework that gives amortized lower bounds on t…
Conditional Hardness for Sensitivity Problems
Monika Henzinger, Andrea Lincoln, Stefan Neumann +1
In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allow…