1 citations · 1 across the 3 of their papers we have counts for
4 papers
Tree Coloring: Random Order and Predictions
Fabian Frei, Matthias Gehnen, Dennis Komm +4
Coloring is a notoriously hard problem, and even more so in the online setting, where each arriving vertex has to be colored immediately and irrevocably. Already on trees, which ar…
Advice Complexity of the Online Induced Subgraph Problem
Dennis Komm, Rastislav Královič, Richard Královič +1
Several well-studied graph problems aim to select a largest (or smallest) induced subgraph with a given property of the input graph. Examples of such problems include maximum indep…
Randomized online computation with high probability guarantees
Dennis Komm, Rastislav Královič, Richard Královič +1
We study the relationship between the competitive ratio and the tail distribution of randomized online minimization problems. To this end, we define a broad class of online problem…
Online Bandwidth Allocation
Michal Forišek, Branislav Katreniak, Jana Katreniaková +6
The paper investigates a version of the resource allocation problem arising in the wireless networking, namely in the OVSF code reallocation process. In this setting a complete bin…