The -server
problem is an online algorithm problem in which
mobile servers occupy points
of a metric space
. Requests arrive one at a time at points
of
, and each request must be served by moving a server
to the requested point before the next request is revealed.
The cost is the total distance traveled by the servers.
An optimal offline algorithm knows the entire request
sequence in advance (Manasse et al. 1990).
The deterministic -server
conjecture (Manasse et al. 1990) asserts that
every metric space admits an online
algorithm with competitive ratio
. For a metric space
with at least
points, no deterministic online
algorithm can have a smaller competitive ratio.
Koutsoupias and Papadimitriou (1995) proved that the work
function algorithm has competitive ratio
at most
.
Coester et al. (2026) reported that the work function algorithm is -competitive on every metric space.
For an initial configuration
and every finite
request sequence
, their claimed bound is
where
and
denote the costs of the work function algorithm
and the optimal offline algorithm, respectively. The
additive term depends only on the initial configuration, so the claimed bound would
establish the deterministic
-server conjecture.
Coester et al. (2026) credit ChatGPT-5.5 Pro and Gemini-3.1 Pro with helping symmetrize a human-designed potential, and GPT-6 Astra with deriving the algebraic
argument for general
and adapting it to a representation supplied by the authors. The authors revised
the resulting proof. As of Sep. 18, 2026, independent
specialist verification and external peer review of the complete proof
had not been reported.