3 papers
cs.DS2025
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…
cs.DS2022
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…
cs.DS2019
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…