The k-Server Conjecture for General Metric Spaces

The k-Server Conjecture for General Metric Spaces

Definitions and mathematical statement

Place $k$ servers in a metric space $(X,d)$. A request sequence $x_1,x_2,\ldots$ is served by moving a server to each requested point; the total cost is the sum of distances moved. An online algorithm chooses moves using only requests already revealed. Let $\mathrm{OPT}(\sigma)$ be the minimum cost of an offline strategy from the same initial configuration. The conjecture asks for a deterministic algorithm with \[ \mathrm{cost}_A(\sigma)\le k\,\mathrm{OPT}(\sigma)+b \] for every finite request sequence, where $b$ may depend on the metric, algorithm and initial configuration but not on $\sigma$. The assertion is for every $k\ge1$ and every metric space. Randomized competitive guarantees are a different target.

Formulation and concept references: [S1].

Short English statement

Can k servers be moved online in any metric space with total cost at most k times the best foresighted strategy, apart from a fixed additive allowance?

Research attempt

Current claim, scope, and process.

This attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. The inherited catalogue metadata and 2022 source [S1] are preserved. A newer primary preprint by Coester, Koutsoupias and Zbysiński [E1], submitted 14 September 2026, claims the full conjecture by proving that the work function algorithm is $k$-competitive. Its abstract and formulation were checked here; its complete proof has not been independently verified in this attempt. Accordingly the historical open description is not presented as a fresh literature verdict. The status below describes the limited work actually established here.

We prove the uniform-metric case and its matching deterministic lower bound, give an unbounded-ratio example for nearest-server greediness, and state the precise amortized inequality needed for a general metric argument. No claimed proof from [E1] is silently imported.

The single-server case and the role of the additive term.

For $k=1$, every feasible strategy must visit the successive requested points. The triangle inequality shows that inserting intermediate moves cannot shorten the distance between two consecutive requests. Moving directly is therefore optimal, and the conjectured ratio one holds with additive constant zero.

For larger $k$, a bound of the form $k\operatorname{OPT}+b$ must use one fixed $b$ for all finite sequences from the specified initial state. An argument proving a separate finite bound for each sequence is insufficient. Conversely an initial relocation whose total cost is fixed independently of the sequence can legitimately be absorbed into $b$.

The model places no computational running-time requirement on the online rule. An expensive but well-defined online optimization is not disqualified merely because its state space is large. The obstacle analyzed below is competitive cost, rather than efficient implementation.

A complete uniform-metric algorithm.

Assume distinct points have distance one and that there are at least $k$ points. Servers can be treated as a cache of $k$ distinct occupied points; any initial duplication can be removed at a fixed cost, which only changes the additive allowance. Use the deterministic marking algorithm.

Within a phase, mark each point when it is requested. On a request to an unoccupied point, move a server from an unmarked occupied point, using a fixed deterministic tie rule. When a request would introduce the $(k+1)$st distinct point of the current phase, clear all marks and begin a new phase with that request.

An eviction is always possible on a miss: if every occupied point were marked, the $k$ marked points would already be occupied and a new distinct request would trigger a new phase. A marked point is never evicted in its phase. Thus each of the at most $k$ distinct phase points causes at most one unit-cost move, and \[ \operatorname{cost}_A(\sigma)\le kP, \tag{262.1} \] where $P$ is the number of nonempty phases. The final phase may have fewer than $k$ points.

An offline lower bound with disjoint charging intervals.

Let $r_j$ be the first request of phase $j$. For each $j<P$, examine the moves made after serving $r_j$ and through the service of $r_{j+1}$. These intervals are disjoint as sets of charged moves.

Phase $j$ contains exactly $k$ distinct requested points, and $r_{j+1}$ lies outside that set. Immediately after serving $r_j$, an offline strategy has a server at $r_j$. During the specified interval it must serve the other $k-1$ phase points and the new point $r_{j+1}$, namely $k$ distinct points different from $r_j$. If it made no positive-cost move, its fixed set of at most $k$ occupied points, already including $r_j$, could not contain all of them. Hence the interval costs at least one in the uniform metric.

Consequently $\operatorname{OPT}(\sigma)\ge P-1$, and $262.1$ gives \[ \operatorname{cost}_A(\sigma)\le k\operatorname{OPT}(\sigma)+k. \tag{262.2} \] This proof does not double-charge a fault at a phase boundary: the move serving $r_{j+1}$ belongs to interval $j$ and is excluded from interval $j+1$. That endpoint convention is important. A vague statement that two consecutive phases contain $k+1$ points would by itself only yield a weaker paired-phase bound.

The argument uses unit distances in both estimates. On a general metric, one expensive eviction can cost far more than the existence of one offline move certifies.

Why the factor $k$ cannot be improved universally.

Use a uniform metric on $k+1$ points and distinct initial server positions. Against any deterministic online algorithm, request an unoccupied point at each step. There is always one, and each service costs at least one, so a length-$T$ sequence costs the algorithm at least $T$. The construction defines a legitimate fixed finite sequence once the deterministic rule is fixed.

For this sequence, construct $k$ offline comparison strategies. Immediately after its first request $p$, arrange their caches so that each misses a different one of the $k$ points other than $p$. Each such configuration is reachable from the common initial cache with cost at most one.

Suppose the last request was $p$ and the next is $q\ne p$. Exactly one comparison cache lacks $q$. In that cache move the server at $p$ to $q$; all other caches make no move. Their omitted points are again all distinct and exclude the new current request. The sum of comparison costs is therefore at most one per subsequent request, plus at most $k$ initially. Repeated identical requests, if present, would cost zero and preserve the argument.

At least one comparison strategy has cost at most $(T-1)/k+1$, so \[ \operatorname{OPT}(\sigma)\le(T-1)/k+1. \] If a deterministic ratio $c<k$ with fixed additive allowance existed on this metric, its inequality would contradict $T\le c((T-1)/k+1)+b$ for sufficiently large $T$. The lower bound concerns deterministic rules; the request-generation argument is not a proof of the same lower bound against an oblivious adversary for randomized algorithms.

Nearest-server greediness can fail by an unbounded amount.

Put two servers at $0$ and $L$ on the real line, with $L>2$, and request $1,0,1,0,\ldots$. Nearest-server greediness always moves the server near zero back and forth by one, leaving the server at $L$ untouched. Its cost equals the sequence length.

An offline strategy moves the server at $L$ to $1$ on the first request and then leaves servers at $0$ and $1$. Its total cost is at most $L-1$, independent of the number of requests. Thus this greedy algorithm has no finite competitive ratio, even with an additive constant depending on this fixed metric and initial state.

The example explains the missing global choice: a large one-time relocation may prevent indefinitely repeated small movements. The triangle inequality does not compare that strategic tradeoff by examining only the next request.

A sufficient potential criterion.

Let $C$ and $O$ be online and offline configurations. Suppose a nonnegative potential $\Phi(C,O)$ has the following two properties. Moving the offline configuration by total distance $d$ while holding $C$ fixed increases $\Phi$ by at most $kd$. After that offline strategy serves a request, the online service of the same request obeys \[ \text{online movement cost}+\Delta\Phi\le0. \tag{262.3} \] Interleave the two services and sum. Telescoping gives \[ \operatorname{cost}_A+\Phi_{\rm final}-\Phi_{\rm initial} \le k\,\operatorname{cost}_O. \] Nonnegativity then proves the desired bound with $b=\Phi_{\rm initial}$. Taking an offline optimum completes the comparison.

This criterion is sufficient, not necessary, and no such potential for arbitrary metrics is constructed here. The source [S1] specifically studies limitations of a potential family, while [E1] introduces a different algebraic approach. Failure of one candidate family does not exclude all possible analyses or invalidate the newer claim.

Verification and outcome.

Finite dynamic programming over all server configurations computes exact offline costs for short sequences on small uniform metrics. The local checks compare marking costs with $262.2$, verify the disjoint phase charge, and test the line example. These computations do not verify the general work-function proof claimed in [E1].

UNRESOLVED in this attempt. The uniform-metric theorem, its sharp deterministic factor, and the greedy counterexample are proved. Extending the amortized argument to arbitrary metrics is the first gap in this written work. The recent full-resolution claim is explicitly recorded for further independent review, rather than either endorsed or omitted.

Sources

• S1 Huang and Zhang, Deterministic 3-Server on a Circle and the Limitation of Canonical Potentials, abstract $2022$. https://arxiv.org/abs/2205.08103. Formulation source.
• E1 Christian Coester, Elias Koutsoupias and Marek Zbysiński, The $k$-server conjecture is true, arXiv:2609.15979v1, 14 September 2026. https://arxiv.org/abs/2609.15979. Recent primary preprint claiming the full deterministic result; formulation checked, full proof not independently verified in this attempt.