12 papers
Competitive Algorithms for Block-Aware Caching
Christian Coester, Roie Levin, Joseph +2
We study the block-aware caching problem, a generalization of classic caching in which fetching (or evicting) pages from the same block incurs the same cost as fetching (or evictin…
Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds
Antonios Antoniadis, Christian Coester, Marek Eliáš +2
We study the online problem of minimizing power consumption in systems with multiple power-saving states. During idle periods of unknown lengths, an algorithm has to choose between…
Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle
Christian Coester, Elias Koutsoupias
The -server conjecture, first posed by Manasse, McGeoch and Sleator in 1988, states that a -competitive deterministic algorithm for the -server problem exists. It is conje…
Online -Taxi via Double Coverage and Time-Reverse Primal-Dual
Niv Buchbinder, Christian Coester, Joseph +1
We consider the online -taxi problem, a generalization of the -server problem, in which servers are located in a metric space. A sequence of requests is revealed one by o…
Learning-Augmented Weighted Paging
Nikhil Bansal, Christian Coester, Ravi Kumar +2
We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The mo…
Metrical Service Systems with Transformations
Sébastien Bubeck, Niv Buchbinder, Christian Coester +1
We consider a generalization of the fundamental online metrical service systems (MSS) problem where the feasible region can be transformed between requests. In this problem, which…