3 papers
cs.DS2026
Online Bisection with Ring Demands
Mateusz Basiak, Marcin Bienkowski, Guy Even +1
The online bisection problem requires maintaining a dynamic partition of nodes into two equal-sized clusters. Requests arrive sequentially as node pairs. If the nodes lie in di…
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.DS2023
An Improved Deterministic Algorithm for the Online Min-Sum Set Cover Problem
Mateusz Basiak, Marcin Bienkowski, Agnieszka Tatarczuk
We study the online variant of the Min-Sum Set Cover (MSSC) problem, a generalization of the well-known list update problem. In the MSSC problem, an algorithm has to maintain the t…