K-server problem

Unsolved problem in computer science:

Is there a ${\displaystyle k}$-competitive algorithm for solving the ${\displaystyle k}$-server problem in an arbitrary metric space?

(more unsolved problems in computer science)

The k-server problem is a problem of theoretical computer science in the category of online algorithms, one of two abstract problems on metric spaces that are central to the theory of competitive analysis (the other being metrical task systems). In this problem, an online algorithm must control the movement of a set of k servers, represented as points in a metric space, and handle requests that are also in the form of points in the space. As each request arrives, the algorithm must determine which server to move to the requested point. The goal of the algorithm is to keep the total distance all servers move small, relative to the total distance the servers could have moved by an optimal adversary who knows in advance the entire sequence of requests.

The problem was first posed by Mark Manasse, Lyle A. McGeoch and Daniel Sleator (1988).^[1] The most prominent open question concerning the k-server problem is the so-called k-server conjecture, also posed by Manasse et al. This conjecture states that there is an algorithm for solving the k-server problem in an arbitrary metric space and for any number k of servers that has competitive ratio exactly k. Manasse et al. were able to prove their conjecture when k = 2, and for more general values of k for some metric spaces restricted to have exactly k+1 points. Chrobak and Larmore (1991) proved the conjecture for tree metrics. The special case of metrics in which all distances are equal is called the paging problem because it models the problem of page replacement algorithms in memory caches, and was also already known to have a k-competitive algorithm (Sleator and Tarjan 1985). Fiat et al. (1990) first proved that there exists an algorithm with finite competitive ratio for any constant k and any metric space, and finally Koutsoupias and Papadimitriou (1995) proved that Work Function Algorithm (WFA) has competitive ratio 2k - 1. However, despite the efforts of many other researchers, reducing the competitive ratio to k or providing an improved lower bound remains open as of 2014^[update]. The most common believed scenario is that the Work Function Algorithm is k-competitive. To this direction, in 2000 Bartal and Koutsoupias showed that this is true for some special cases (if the metric space is a line, a weighted star or any metric of k+2 points).

The k-server conjecture has also a version for randomized algorithms, which asks if exists a randomized algorithm with competitive ratio O(log k) in any arbitrary metric space (with at least k + 1 points).^[2] In 2011, a randomized algorithm with competitive bound Õ(log²k log³n) was found.^[3][4] In 2017, a randomized algorithm with competitive bound O(log⁶ k) was announced,^[5] but was later retracted.^[6] In 2022 it was shown that the randomized version of the conjecture is false.^[2][7][8]