2 citations · 2 across the 2 of their papers we have counts for
9 papers · 1 filter
Deterministic Self-Adjusting Tree Networks Using Rotor Walks
Chen Avin, Marcin Bienkowski, Iosif Salem +3
We revisit the design of self-adjusting single-source tree networks. The problem can be seen as a generalization of the classic list update problem to trees, and finds applications…
Improved Analysis of Online Balanced Clustering
Marcin Bienkowski, Martin Böhm, Martin Koutecký +3
In the online balanced graph repartitioning problem, one has to maintain a clustering of nodes into clusters, each having nodes. During runtime, an online…
Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu
We present a unified framework for minimizing average completion time for many seemingly disparate online scheduling problems, such as the traveling repairperson problems (TRP), di…
A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
Marcin Bienkowski, Björn Feldkord, Paweł Schmidt
In the online non-metric variant of the facility location problem, there is a given graph consisting of a set of facilities (each with a certain opening cost), a set of pot…
An Optimal Algorithm for Online Multiple Knapsack
Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch
In the online multiple knapsack problem, an algorithm faces a stream of items, and each item has to be either rejected or stored irrevocably in one of bins (knapsacks) of equal…
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…