Mateusz Basiak

dblp:350/4862 · DBLP profile ↗
← Back
3ranked-venue papers
3as first author
3since 2021 · last 2026
0009-0009-0210-6451ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 first-author · 3 since 2021
YearPublicationVenuePosition
2026 Online Bisection with Ring Demands
Mateusz Basiak, Marcin Bienkowski, Guy Even, Agnieszka Tatarczuk
SIROCCO1
2025 A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs
abstract
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 requested item with previous items for free. We construct an online algorithm Full-Or-Partial-Move (FPM), whose competitive ratio is at most 3.3904, improving over the previous best known bound of 4.
Mateusz Basiak, Marcin Bienkowski, Martin Böhm 0001, Marek Chrobak, Lukasz Jez, Jirí Sgall, Agnieszka Tatarczuk
ESA1
2023 An Improved Deterministic Algorithm for the Online Min-Sum Set Cover Problem
Mateusz Basiak, Marcin Bienkowski, Agnieszka Tatarczuk
WAOA1