4 papers
Pure Tail Constraints for Online Problems
Mateusz Basiak, Marcin Bienkowski, Yongho Shin +1
Controlling tail risk is an important objective in online optimization, and recently it has been studied in the context of competitive analysis. Continuing this line of research, w…
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…
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…
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…