4 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…
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…
Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics
Marcin Bienkowski, Łukasz Jeż, Paweł Schmidt
The generalized -server problem is an extension of the weighted -server problem, which in turn extends the classic -server problem. In the generalized -server problem,…
A Primal-Dual Online Deterministic Algorithm for Matching with Delays
Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu +1
In the Min-cost Perfect Matching with Delays (MPMD) problem, 2 m requests arrive over time at points of a metric space. An online algorithm has to connect these requests in pairs,…