22 citations · 55 across the 17 of their papers we have counts for
5 papers · 1 filter
The -server conjecture is true
Christian Coester, Elias Koutsoupias, Marek Zbysiński
The -server conjecture states that a deterministic online algorithm can achieve competitive ratio on every metric space. We prove the conjecture. Specifically, we show that…
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…
Better Bounds for Online Line Chasing
Marcin Bienkowski, Jarosław Byrka, Marek Chrobak +3
We study online competitive algorithms for the \emph{line chasing problem} in Euclidean spaces , where the input consists of an initial point and a sequence of line…
The Online -Taxi Problem
Christian Coester, Elias Koutsoupias
We consider the online -taxi problem, a generalization of the -server problem, in which taxis serve a sequence of requests in a metric space. A request consists of two po…
The Infinite Server Problem
Christian Coester, Elias Koutsoupias, Philip Lazos
We study a variant of the -server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a s…