1 citations · 1 across the 4 of their papers we have counts for
6 papers
Unary Versus Binary Two-Way Automata
Viliam Geffert, Vincent Hlaváč, Rastislav Královič
If L is a unary language, then its binary coded version bin(L) is a binary language containing all binary strings representing any 0^x in L. It is known that if a unary language L…
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…
Point-to-set Principle and Constructive Dimension Faithfulness
Satyadev Nandakumar, Subin Pulari, Akhil S
Hausdorff -dimension is a notion of Hausdorff dimension developed using a restricted class of coverings of a set. We introduce an effective version of Hausdorff -dimension, w…
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…