3 papers
cs.DS2024
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…
cs.DS2013
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…
cs.DS2007
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…