2 citations · 2 across the 3 of their papers we have counts for
5 papers
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
Mateusz Basiak, Marcin Bienkowski, Martin Böhm +4
We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the ``standard'' model, in which an algorithm is allowed to swap the requ…
Online Disjoint Set Covers: Randomization is not Necessary
Marcin Bienkowski, Jarosław Byrka, Łukasz Jeż
In the online disjoint set covers problem, the edges of a hypergraph are revealed online, and the goal is to partition them into a maximum number of disjoint set covers. That is, n…
Lower bounds on the performance of online algorithms for relaxed packing problems
János Balogh, György Dósa, Leah Epstein +1
We prove new lower bounds for suitable competitive ratio measures of two relaxed online packing problems: online removable multiple knapsack, and a recently introduced online minim…
Unbounded lower bound for k-server against weak adversaries
Marcin Bienkowski, Jarosław Byrka, Christian Coester +1
We study the resource augmented version of the -server problem, also known as the -server problem against weak adversaries or the -server problem. In this setting, an…
A 4/3-competitive randomized algorithm for online scheduling of packets with agreeable deadlines
Łukasz Jeż
In 2005 Li et al. gave a phi-competitive deterministic online algorithm for scheduling of packets with agreeable deadlines with a very interesting analysis. This is known to be opt…