The k-server conjecture is true

# The 𝑘-server conjecture is true
Source: [https://arxiv.org/html/2609.15979](https://arxiv.org/html/2609.15979)
September 14, 2026

###### Abstract

Thekk\-server conjecture states that a deterministic online algorithm can achieve competitive ratiokkon every metric space\. We prove the conjecture\. Specifically, we show that the work function algorithm satisfies it\.

Our proof uses a natural algebraic representation of the work function as a matrix, which encodes all feasible paths to reach a configuration\. In this representation, the minimum and addition operations arising in the definition of optimal costs correspond to addition and multiplication of formal expressions, and each work function value corresponds to the determinant ofkkcolumns of the matrix\. A request arrival updates the representation via a change of basis and row replacement\. The amortized analysis is based on a potential function defined in terms of a larger matrix whose coordinates are pairs of coordinates of the original matrix representation\.

## 1Introduction

Thekk\-server problem, introduced by Manasse, McGeoch and Sleator\[[53](https://arxiv.org/html/2609.15979#bib.bib48)\], is a central problem in competitive analysis\. It has been repeatedly referred to as the “holy grail” of the field\[[21](https://arxiv.org/html/2609.15979#bib.bib21),[4](https://arxiv.org/html/2609.15979#bib.bib4),[33](https://arxiv.org/html/2609.15979#bib.bib33),[51](https://arxiv.org/html/2609.15979#bib.bib47),[26](https://arxiv.org/html/2609.15979#bib.bib28),[28](https://arxiv.org/html/2609.15979#bib.bib27),[40](https://arxiv.org/html/2609.15979#bib.bib38),[32](https://arxiv.org/html/2609.15979#bib.bib32),[41](https://arxiv.org/html/2609.15979#bib.bib39),[16](https://arxiv.org/html/2609.15979#bib.bib16)\], and many techniques originally developed for thekk\-server problem have gone on to impact various other problems in online algorithms\. The problem’s definition is simple: There arekkservers located at points of a metric space\. At each time step, a request arrives at a point of the metric space\. An online algorithm must serve the request immediately by moving a server to the requested location, without knowledge of future requests\. The goal is to minimize the total distance traveled by servers\.

When introducing the problem,\[[53](https://arxiv.org/html/2609.15979#bib.bib48)\]showed that the competitive ratio of any deterministic online algorithm is at leastkkon every metric space withn\>kn\>kpoints, showed that this is tight whenk=2k=2orn=k\+1n=k\+1, and conjectured that it is tight in general\. This question became known as the*kk\-server conjecture*, and has been a driving force for progress in competitive analysis\. The first algorithm with a finite competitive ratio on general metrics was obtained in\[[38](https://arxiv.org/html/2609.15979#bib.bib36)\], achieving a competitive ratio exponential inkk\. This was improved to a smaller exponential using the \(randomized\) Harmonic algorithm in\[[42](https://arxiv.org/html/2609.15979#bib.bib40)\]and\[[8](https://arxiv.org/html/2609.15979#bib.bib8)\], which can be derandomized using the techniques of\[[11](https://arxiv.org/html/2609.15979#bib.bib11)\]\. A substantial improvement was achieved by Koutsoupias and Papadimitriou\[[47](https://arxiv.org/html/2609.15979#bib.bib45)\], who showed that the*work function algorithm \(WFA\)*is\(2​k−1\)\(2k\-1\)\-competitive on general metrics\. Another proof of this result was given in\[[49](https://arxiv.org/html/2609.15979#bib.bib60)\]\.

The WFA was introduced in\[[25](https://arxiv.org/html/2609.15979#bib.bib25)\], and proposed independently also by Karloff and by McGeoch and Sleator\. Its definition is simple and generic, and extends far beyond thekk\-server problem: For a configurationXX\(e\.g\., the positions ofkkservers in thekk\-server problem\) and timett, denote bywt​\(X\)w\_\{t\}\(X\)the minimal \(offline\) cost to serve the requests up to timettand then end up at configurationXX\. The functionwtw\_\{t\}is called the work function, and its values can be computed online at timett\. WFA moves at each time to the configuration that minimizes the sum of its work function value plus the cost \(distance\) of moving there from the previous configuration\.

The conjectured bound ofkkwas established for WFA in many special cases, includingk=2k=2\[[25](https://arxiv.org/html/2609.15979#bib.bib25)\],n=k\+1n=k\+1\(folklore, cf\.\[[50](https://arxiv.org/html/2609.15979#bib.bib43)\]\),n=k\+2n=k\+2\[[48](https://arxiv.org/html/2609.15979#bib.bib46)\], line metrics\[[9](https://arxiv.org/html/2609.15979#bib.bib9)\], weighted stars\[[9](https://arxiv.org/html/2609.15979#bib.bib9)\]\(equivalent to the weighted paging problem\), multirays\[[28](https://arxiv.org/html/2609.15979#bib.bib27)\],k=3k=3in the Manhattan plane\[[10](https://arxiv.org/html/2609.15979#bib.bib10)\],k=3k=3on trees\[[28](https://arxiv.org/html/2609.15979#bib.bib27)\], andk=3k=3on circles\[[44](https://arxiv.org/html/2609.15979#bib.bib42)\]\. Additionally, the Double Coverage algorithm achieves the conjectured bound ofkkon the line\[[23](https://arxiv.org/html/2609.15979#bib.bib23)\]and, more generally, trees\[[24](https://arxiv.org/html/2609.15979#bib.bib24)\]\. We show that WFA iskk\-competitive on general metric spaces, thereby confirming thekk\-server conjecture\.

### 1\.1Preliminaries and our result

Thekk\-server problem is defined on a metric space\(ℳ,d\)\(\\mathcal\{M\},d\)\. There arekkservers starting at locationss1,…,sk∈ℳs\_\{1\},\\dots,s\_\{k\}\\in\\mathcal\{M\}, and a sequence of requestsr1,…,rT∈ℳr\_\{1\},\\dots,r\_\{T\}\\in\\mathcal\{M\}is revealed online\. For convenience, we writeM:=\{s1,…,sk,r1,…,rT\}M:=\\\{s\_\{1\},\\dots,s\_\{k\},r\_\{1\},\\dots,r\_\{T\}\\\}for the corresponding set ofk\+Tk\+Tdistinct location labels\. Thenddinduces a pseudometric onMM; the reason it may only be a pseudometric rather than a metric is thatMMcan contain distinct labels for the same point at distance zero\.

A configuration is akk\-element subset ofMM, representing the locations ofkkservers\. For configurationsX=\{x1,…,xk\}X=\\\{x\_\{1\},\\ldots,x\_\{k\}\\\}andY=\{y1,…,yk\}Y=\\\{y\_\{1\},\\ldots,y\_\{k\}\\\}, their distance is

D⁡\(X,Y\)=min⁡∑i=1kσ∈Sk⁡d⁡\(xi,yσ⁡\(i\)\)\.D\(X,Y\)=\\min\_\{\\sigma\\in S\_\{k\}\}\\sum\_\{i=1\}^\{k\}d\(x\_\{i\},y\_\{\\sigma\(i\)\}\)\.\(1\)This is the minimum cost of moving the servers fromXXtoYY\.

Denote the initial configuration byC0=\{s1,…,sk\}C\_\{0\}=\\\{s\_\{1\},\\ldots,s\_\{k\}\\\}\. At each timett, the algorithm must serve the current requestrtr\_\{t\}by moving to a configurationCt∋rtC\_\{t\}\\ni r\_\{t\}, paying movement costD⁡\(Ct−1,Ct\)D\(C\_\{t\-1\},C\_\{t\}\)\. The goal is to minimize the total cost\.

The work function is the functionwtw\_\{t\}that maps a configurationXXto the minimum \(offline\) cost to serve the firstttrequests and then move to configurationXX\. It is well\-known \(see, e\.g\.,\[[50](https://arxiv.org/html/2609.15979#bib.bib43)\]\) that the work function can be computed online by dynamic programming, viaw0​\(X\)=D⁡\(C0,X\)w\_\{0\}\(X\)=D\(C\_\{0\},X\)and the recurrence

wt​\(X\)=\{wt−1​\(X\),rt∈X,minx∈X⁡\{wt−1​\(X−x\+rt\)\+d⁡\(rt,x\)\},rt∉X\.w\_\{t\}\(X\)=\\begin\{cases\}w\_\{t\-1\}\(X\),&r\_\{t\}\\in X,\\\\\[2\.0pt\] \\displaystyle\\min\_\{x\\in X\}\\bigl\\\{w\_\{t\-1\}\(X\-x\+r\_\{t\}\)\+d\(r\_\{t\},x\)\\bigr\\\},&r\_\{t\}\\notin X\.\\end\{cases\}\(2\)Thus, the total optimal offline cost can be written asOPTC0⁡\(r1,…,rT\)=minX⁡wT​\(X\)\\OPT\_\{C\_\{0\}\}\(r\_\{1\},\\ldots,r\_\{T\}\)=\\min\_\{X\}w\_\{T\}\(X\)\.

The work function algorithm \(WFA\) serves the request at timettin a configurationCt∋rtC\_\{t\}\\ni r\_\{t\}minimizingwt​\(Ct\)\+D⁡\(Ct−1,Ct\)w\_\{t\}\(C\_\{t\}\)\+D\(C\_\{t\-1\},C\_\{t\}\)\. For simplicity, we assume here a lazy implementation withCt⊆Ct−1∪\{rt\}C\_\{t\}\\subseteq C\_\{t\-1\}\\cup\\\{r\_\{t\}\\\}, although our result extends to any other tie\-breaking rule\. We denote the cost of WFA on a request sequenceσ\\sigmabyWFAC0⁡\(σ\)\\WFA\_\{C\_\{0\}\}\(\\sigma\)\.

The following standard accounting argument is the extended\-cost method of Chrobak and Larmore\[[25](https://arxiv.org/html/2609.15979#bib.bib25)\]: Instead of bounding directly the costD⁡\(Ct−1,Ct\)D\(C\_\{t\-1\},C\_\{t\}\)of WFA, we bound the so\-called extended costmaxX⁡\(wt​\(X\)−wt−1​\(X\)\)\\max\_\{X\}\(w\_\{t\}\(X\)\-w\_\{t\-1\}\(X\)\)\. We include its proof in the appendix for completeness\.

###### Lemma 1\.1\(Extended\-cost accounting\[[25](https://arxiv.org/html/2609.15979#bib.bib25)\]\)\.

LetC0,C1,…,CTC\_\{0\},C\_\{1\},\\ldots,C\_\{T\}be any WFA trajectory, and letExtCostt=maxX⁡\(wt​\(X\)−wt−1​\(X\)\)\\mathrm\{ExtCost\}\_\{t\}=\\max\_\{X\}\(w\_\{t\}\(X\)\-w\_\{t\-1\}\(X\)\)\. Then

WFAC0⁡\(r1,…,rT\)\+wT​\(CT\)≤∑t=1TExtCostt\.\\WFA\_\{C\_\{0\}\}\(r\_\{1\},\\ldots,r\_\{T\}\)\+w\_\{T\}\(C\_\{T\}\)\\leq\\sum\_\{t=1\}^\{T\}\\mathrm\{ExtCost\}\_\{t\}\.\(3\)

For a configurationX=\{x1,…,xk\}X=\\\{x\_\{1\},\\ldots,x\_\{k\}\\\}, define its clique weight by

cl⁡\(X\)=∑1≤i<j≤kd⁡\(xi,xj\)\.\\cl\(X\)=\\sum\_\{1\\leq i<j\\leq k\}d\(x\_\{i\},x\_\{j\}\)\.
The following theorem establishes thekk\-server conjecture\.

###### Theorem 1\.2\.

Let\(ℳ,d\)\(\\mathcal\{M\},d\)be any metric space, and letC0=\{s1,…,sk\}C\_\{0\}=\\\{s\_\{1\},\\ldots,s\_\{k\}\\\}be the initial configuration\. For every finite request sequenceσ\\sigma, the work function algorithm satisfies

WFAC0⁡\(σ\)≤k​OPTC0⁡\(σ\)\+cl⁡\(C0\)\.\\WFA\_\{C\_\{0\}\}\(\\sigma\)\\leq k\\,\\OPT\_\{C\_\{0\}\}\(\\sigma\)\+\\cl\(C\_\{0\}\)\.

### 1\.2Overview of the proof

By Lemma[1\.1](https://arxiv.org/html/2609.15979#S1.Thmtheorem1), it suffices to prove

∑t=1TExtCostt≤\(k\+1\)​wT​\(XT\)\+cl⁡\(C0\)−cl⁡\(XT\),\\sum\_\{t=1\}^\{T\}\\mathrm\{ExtCost\}\_\{t\}\\leq\(k\+1\)w\_\{T\}\(X\_\{T\}\)\+\\cl\(C\_\{0\}\)\-\\cl\(X\_\{T\}\),whereXTX\_\{T\}is the final optimal offline configuration satisfyingOPTC0⁡\(σ\)=wT​\(XT\)\\OPT\_\{C\_\{0\}\}\(\\sigma\)=w\_\{T\}\(X\_\{T\}\)\. To prove this bound, it is enough to prove that there exists a potential functionΨt\\Psi\_\{t\}which satisfies

Ψ0=−cl⁡\(C0\),ExtCostt≤Ψt−Ψt−1,Ψt≤\(k\+1\)​wt​\(X\)−cl⁡\(X\)\\Psi\_\{0\}=\-\\cl\(C\_\{0\}\),\\qquad\\mathrm\{ExtCost\}\_\{t\}\\leq\\Psi\_\{t\}\-\\Psi\_\{t\-1\},\\qquad\\Psi\_\{t\}\\leq\(k\+1\)w\_\{t\}\(X\)\-\\cl\(X\)\(4\)for every configurationXX\. In order to represent the potential, we need a more complex algebraic structure than the numerical work function\.

We introduce a novel approach which has been standard in the theory of valuated matroids, but has not been previously used for proving the competitiveness of the WFA\. We use the fraction field𝕂\\mathbb\{K\}which extends the set of formal sums of the form∑a∈Afa​za\\sum\_\{a\\in A\}f\_\{a\}z^\{a\}, whereA⊂ℝA\\subset\\mathbb\{R\}is finite\. We can define the valuationν\\nuof a formal sum to be the smallest exponent of the free variablezzwith a nonzero coefficient\. For exampleν⁡\(7​z3\+4​z6\)=3\\nu\(7z^\{3\}\+4z^\{6\}\)=3\. The definition extends to the fraction field𝕂\\mathbb\{K\}byν⁡\(f/g\)=ν⁡\(f\)−ν⁡\(g\)\\nu\(f/g\)=\\nu\(f\)\-\\nu\(g\)\. This function satisfies the following properties:

ν⁡\(a​b\)=ν⁡\(a\)\+ν⁡\(b\),ν⁡\(a\+b\)≥min⁡\{ν⁡\(a\),ν⁡\(b\)\}\.\\nu\(ab\)=\\nu\(a\)\+\\nu\(b\),\\qquad\\nu\(a\+b\)\\geq\\min\\\{\\nu\(a\),\\nu\(b\)\\\}\.Since the work function recurrence is defined by taking minimums of sums, using𝕂\\mathbb\{K\}andν\\nuare natural candidates for alternative expression of the work function involving ordinary multiplication and addition instead\.

To express the current state of the work function, we maintain vectorsqx∈𝕂kq\_\{x\}\\in\\mathbb\{K\}^\{k\}for every pointxx\. In Section[2](https://arxiv.org/html/2609.15979#S2), we prove that the current work functionwwcan be represented usingqxq\_\{x\}:

w⁡\(\{x1,…,xk\}\)=ν⁡\(det\(qx1,…,qxk\)\)w\(\\\{x\_\{1\},\\dots,x\_\{k\}\\\}\)=\\nu\(\\det\(q\_\{x\_\{1\}\},\\ldots,q\_\{x\_\{k\}\}\)\)Upon arrival of a requestrr, we update the representation by performing the following operations:

1. 1\.Change the vector space basis so thatqr=e1q\_\{r\}=e\_\{1\}is a base vector and the determinants are preserved\.
2. 2\.Replace the first coordinate of everyqxq\_\{x\}in the new basis by a value proportional tozd⁡\(r,x\)z^\{d\(r,x\)\}with valuationd⁡\(r,x\)d\(r,x\), with a coefficient that prevents the value to be cancelled out by the determinant\. This is achieved by including sufficiently many independent coefficient variables in the field\.

We can now consider the problem only in its algebraic form as the work function and extended cost can be represented using only the vectorsqxq\_\{x\}and their transformations\. We use a potential based on the quadratic productqx​qyq\_\{x\}q\_\{y\}, which is a\(k\+12\)\\binom\{k\+1\}\{2\}\-dimensional vector with coordinates indexed by pairs\(i,j\)\(i,j\)withi≤ji\\leq j, whose entries are obtained by taking products of the entries ofqxq\_\{x\}andqyq\_\{y\}in the respective coordinates\. The potential isΨ=μ⁡\(𝒬\)\\Psi=\\mu\(\\mathcal\{Q\}\)where𝒬=\[z−d⁡\(x,y\)​qx​qy\]x≤y\\mathcal\{Q\}=\[\\,z^\{\-d\(x,y\)\}q\_\{x\}q\_\{y\}\\,\]\_\{x\\leq y\}andμ⁡\(G\)=min1≤i1<⋯<id≤m⁡ν⁡\(det\(gi1,…,gid\)\)\\mu\(G\)=\\min\_\{1\\leq i\_\{1\}<\\cdots<i\_\{d\}\\leq m\}\\nu\(\\det\(g\_\{i\_\{1\}\},\\ldots,g\_\{i\_\{d\}\}\)\)\. Thez−d⁡\(x,y\)z^\{\-d\(x,y\)\}term and theμ\\mufunction draw parallel to previously known potentials for proving the competitiveness of certain cases of the WFA\. The other potentials have also used the selection of a subset of points to minimize an expression which contains the work function values, here expressed indirectly usingqxq\_\{x\}, and the distance pairs of used points with negative sign, here expressed usingz−d⁡\(x,y\)z^\{\-d\(x,y\)\}\.

The check that the potential satisfiesΨt≤\(k\+1\)​wt​\(X\)−cl⁡\(X\)\\Psi\_\{t\}\\leq\(k\+1\)w\_\{t\}\(X\)\-\\cl\(X\)for anyXXandΨ0=−cl⁡\(C0\)\\Psi\_\{0\}=\-\\cl\(C\_\{0\}\)is a relatively straightforward computation shown in Lemmas[5\.1](https://arxiv.org/html/2609.15979#S5.Thmtheorem1)and[5\.2](https://arxiv.org/html/2609.15979#S5.Thmtheorem2)respectively\.

The heart of the proof is showing that the potential satisfiesExtCostt≤Ψt−Ψt−1\\mathrm\{ExtCost\}\_\{t\}\\leq\\Psi\_\{t\}\-\\Psi\_\{t\-1\}\. In Section[4](https://arxiv.org/html/2609.15979#S4), we prove this by introducing inequalities regarding the current potential, the new potential and the extended cost\. They all follow from the definition of the algebraic handling of a requestrr\.

### 1\.3Related work

#### Related problems\.

Thekk\-server problem is closely related to a number of other online problems\. For example, the paging \(aka caching\) problem corresponds to the special case where the metric space is a uniform metric, and was foundational for the field of competitive analysis\[[61](https://arxiv.org/html/2609.15979#bib.bib53)\]\. Thekk\-server problem further belongs to the class of metrical task systems\[[15](https://arxiv.org/html/2609.15979#bib.bib15),[19](https://arxiv.org/html/2609.15979#bib.bib17),[29](https://arxiv.org/html/2609.15979#bib.bib29),[17](https://arxiv.org/html/2609.15979#bib.bib20)\], andkk\-server on a\(k\+1\)\(k\+1\)\-point metric is equivalent to metrical service systems\[[25](https://arxiv.org/html/2609.15979#bib.bib25),[17](https://arxiv.org/html/2609.15979#bib.bib20)\], with further close connections to layered graph traversal\[[36](https://arxiv.org/html/2609.15979#bib.bib37),[18](https://arxiv.org/html/2609.15979#bib.bib19),[31](https://arxiv.org/html/2609.15979#bib.bib31)\]\. Generalizations of thekk\-server problem include the weighted and the generalizedkk\-server problem\[[39](https://arxiv.org/html/2609.15979#bib.bib35),[59](https://arxiv.org/html/2609.15979#bib.bib52),[7](https://arxiv.org/html/2609.15979#bib.bib6),[6](https://arxiv.org/html/2609.15979#bib.bib7),[13](https://arxiv.org/html/2609.15979#bib.bib14)\], the infinite server problem\[[26](https://arxiv.org/html/2609.15979#bib.bib28),[12](https://arxiv.org/html/2609.15979#bib.bib12)\], and thekk\-taxi problem\[[27](https://arxiv.org/html/2609.15979#bib.bib26),[43](https://arxiv.org/html/2609.15979#bib.bib41),[30](https://arxiv.org/html/2609.15979#bib.bib30)\]\.

#### Work functions and WFA\.

The WFA \(and a parametrized variant where the work function term is scaled by a constant factor\) have been applied to many other problems, including metrical task systems\[[14](https://arxiv.org/html/2609.15979#bib.bib13)\], layered graph traversal\[[22](https://arxiv.org/html/2609.15979#bib.bib22)\], list update\[[1](https://arxiv.org/html/2609.15979#bib.bib1)\], matching\[[46](https://arxiv.org/html/2609.15979#bib.bib44)\], generalizedkk\-server\[[60](https://arxiv.org/html/2609.15979#bib.bib51)\]\. Moreover, work functions have been instrumental to advancements on convex body chasing\[[58](https://arxiv.org/html/2609.15979#bib.bib50),[2](https://arxiv.org/html/2609.15979#bib.bib2)\]\. Variants of WFA have further been proposed as candidates for addressing thekk\-taxi problem\[[27](https://arxiv.org/html/2609.15979#bib.bib26)\]and the dynamic optimality conjecture\[[60](https://arxiv.org/html/2609.15979#bib.bib51)\]\.

#### Quasiconvexity, valuated matroids, and tropical geometry\.

An important property ofkk\-server work functions is*quasiconvexity*, which was introduced in the online algorithms context by Koutsoupias and Papadimitriou\[[47](https://arxiv.org/html/2609.15979#bib.bib45)\]\. However, equivalent or closely related notions have appeared independently across several fields under different terminology\. In fact, quasiconvex work functions in thekk\-server setting are mathematically equivalent to*valuated matroids*, a concept introduced by Dress and Wenzel\[[34](https://arxiv.org/html/2609.15979#bib.bib55)\]in connection with a variant of the greedy algorithm\. In economics, Kelso and Crawford\[[45](https://arxiv.org/html/2609.15979#bib.bib54)\]introduced the closely related*gross substitutes*condition as a sufficient condition for the existence of Walrasian equilibria\. These structures also play a central role in discrete optimization through their equivalence toM♮M^\{\\natural\}\-concave functions\[[55](https://arxiv.org/html/2609.15979#bib.bib57)\]\.

The foundational paper by Dress and Wenzel on valuated matroids\[[35](https://arxiv.org/html/2609.15979#bib.bib56)\]shows that valuated matroids arise naturally from valuations of determinants and Plücker relations\. This relationship has since been further expanded by advances in tropical geometry \(see for example, Speyer and Sturmfels\[[62](https://arxiv.org/html/2609.15979#bib.bib58)\]and Maclagan and Sturmfels\[[52](https://arxiv.org/html/2609.15979#bib.bib59)\]\)\.

#### Randomizedkk\-server\.

A separate direction for thekk\-server problem concerns randomized algorithms \(against oblivious adversaries\): In this setting, a competitive ratio ofO⁡\(log⁡k\)O\(\\log k\)is known to be achievable on uniform metrics\[[37](https://arxiv.org/html/2609.15979#bib.bib34)\]and weighted stars\[[5](https://arxiv.org/html/2609.15979#bib.bib5)\], matching anΩ⁡\(log⁡k\)\\Omega\(\\log k\)lower bound that holds on every metric ofn\>kn\>kpoints\[[17](https://arxiv.org/html/2609.15979#bib.bib20)\]\. The*randomizedkk\-server conjecture*, which states that aO⁡\(log⁡k\)O\(\\log k\)\-competitive randomized algorithm exists for all metric spaces, was refuted in\[[17](https://arxiv.org/html/2609.15979#bib.bib20)\]by anΩ⁡\(log2⁡k\)\\Omega\(\\log^\{2\}k\)lower bound that holds on some metric spaces, even whenn=k\+1n=k\+1\. A first polylog\(k,n\)\(k,n\)\-competitive algorithm for arbitrarynn\-point metrics was achieved in\[[3](https://arxiv.org/html/2609.15979#bib.bib3)\], and improved toO⁡\(log⁡n​log2​k\)O\(\\log n\\log^\{2\}k\)andO⁡\(log⁡Δ​log3​k\)O\(\\log\\Delta\\log^\{3\}k\)in\[[20](https://arxiv.org/html/2609.15979#bib.bib18)\], whereΔ\\Deltais the ratio between the largest and smallest non\-zero distance of the metric space\. Since bothnnandΔ\\Deltacan be infinite, it remains unknown whether randomization provides an advantage on general metric spaces, and the best known competitive ratio even when randomization is allowed is achieved by WFA\.

## 2From min\-plus recurrences to determinant columns

This section develops the algebraic state from first principles\. Throughout,zzis a formal symbol and its exponents represent costs\. Se use additional variables as coefficients to distinguish combinatorial choices; their values are never specialized to numbers\. We give configurations an ordering whenever they are used to index determinant columns\.

### 2\.1Formal expressions and their lowest exponents

For each initial server indexi∈\[k\]i\\in\[k\]and location labelx∈Mx\\in M, introduce an independent variableγi,x\\gamma\_\{i,x\}\. For each timet∈\[T\]t\\in\[T\]and labelx∈Mx\\in M, introduce an independent variableξt,x\\xi\_\{t,x\}\. Let𝔽\\mathbb\{F\}be the field of rational functions overℚ\\mathbb\{Q\}in all these variables\.

Consider finite formal sums

f=∑a∈Afa​za,A⊆ℝ​finite,fa∈𝔽\.f=\\sum\_\{a\\in A\}f\_\{a\}z^\{a\},\\qquad A\\subseteq\\mathbb\{R\}\\text\{ finite\},\\quad f\_\{a\}\\in\\mathbb\{F\}\.Combine equal exponents when adding, and multiply usingza​zb=za\+bz^\{a\}z^\{b\}=z^\{a\+b\}\. Iff≠0f\\neq 0, define

ν⁡\(f\)=min⁡\{a:fa≠0\};ν⁡\(0\)=∞\.\\nu\(f\)=\\min\\\{a:f\_\{a\}\\neq 0\\\};\\qquad\\nu\(0\)=\\infty\.For instance,ν⁡\(3​z2−7​z5\)=2\\nu\(3z^\{2\}\-7z^\{5\}\)=2andν⁡\(z−1\+z4\)=−1\\nu\(z^\{\-1\}\+z^\{4\}\)=\-1\. Every nonzero element of the coefficient field𝔽\\mathbb\{F\}has valuation zero\.

The least\-exponent term in a product of two nonzero sums is the product of their least\-exponent terms\. Its coefficient is nonzero because𝔽\\mathbb\{F\}is a field\. Therefore these finite sums have no zero divisors\. We may form their fraction field𝕂\\mathbb\{K\}and extend the definition by

ν⁡\(f/g\)=ν⁡\(f\)−ν⁡\(g\)\(f​g≠0\)\.\\nu\(f/g\)=\\nu\(f\)\-\\nu\(g\)\\qquad\(fg\\neq 0\)\.This is well defined: iff/g=f′/g′f/g=f^\{\\prime\}/g^\{\\prime\}, thenf​g′=f′​gfg^\{\\prime\}=f^\{\\prime\}g, and taking least exponents of these products gives the same difference\. The two rules we will use are

ν⁡\(a​b\)=ν⁡\(a\)\+ν⁡\(b\),ν⁡\(a\+b\)≥min⁡\{ν⁡\(a\),ν⁡\(b\)\}\.\\nu\(ab\)=\\nu\(a\)\+\\nu\(b\),\\qquad\\nu\(a\+b\)\\geq\\min\\\{\\nu\(a\),\\nu\(b\)\\\}\.\(5\)The second inequality can be strict\. For example,z2\+\(−z2\+z5\)=z5z^\{2\}\+\(\-z^\{2\}\+z^\{5\}\)=z^\{5\}\. It is precisely this cancellation issue that requires care when replacing a min\-plus recurrence by an algebraic one\.

###### Lemma 2\.1\(Fresh coefficients prevent cancellation\)\.

Supposef1,…,fm∈𝕂f\_\{1\},\\ldots,f\_\{m\}\\in\\mathbb\{K\}use none of the independent coefficient variablesη1,…,ηm\\eta\_\{1\},\\ldots,\\eta\_\{m\}\. For real numbersa1,…,ama\_\{1\},\\ldots,a\_\{m\}, if at least onefif\_\{i\}is nonzero, then

ν⁡\(∑i=1mηi​zai​fi\)=mini⁡\(ai\+ν⁡\(fi\)\)\.\\nu\\left\(\\sum\_\{i=1\}^\{m\}\\eta\_\{i\}z^\{a\_\{i\}\}f\_\{i\}\\right\)=\\min\_\{i\}\\bigl\(a\_\{i\}\+\\nu\(f\_\{i\}\)\\bigr\)\.

###### Proof\.

Put thefif\_\{i\}over a common nonzero denominator that uses none of theηi\\eta\_\{i\}\. After this multiplication, all terms are finite sums\. At the smallest exponent occurring on the right, the coefficient on the left is a nonempty sum∑i∈Iηi​bi\\sum\_\{i\\in I\}\\eta\_\{i\}b\_\{i\}, with nonzerobib\_\{i\}independent of all theηj\\eta\_\{j\}\. It cannot be zero: after clearing coefficient denominators it is a nonzero polynomial, linear in distinct independent variablesηi\\eta\_\{i\}\. Dividing by the common denominator gives the assertion\. ∎

### 2\.2The initial matching as a determinant

For every labelx∈Mx\\in M, including the initial labels themselves, define a columnqx∈𝕂kq\_\{x\}\\in\\mathbb\{K\}^\{k\}by

\(qx\)i=γi,x​zd⁡\(si,x\),i∈\[k\]\.\(q\_\{x\}\)\_\{i\}=\\gamma\_\{i,x\}z^\{d\(s\_\{i\},x\)\},\\qquad i\\in\[k\]\.\(6\)Thus one uniform formula defines all columns\. IfX=\(x1,…,xk\)X=\(x\_\{1\},\\ldots,x\_\{k\}\)has distinct labels, put

u0​\(X\)=det\(qx1,…,qxk\)\.u\_\{0\}\(X\)=\\det\(q\_\{x\_\{1\}\},\\ldots,q\_\{x\_\{k\}\}\)\.The determinant expansion is

u0​\(X\)=∑σ∈Sksgn⁡\(σ\)​\(∏i=1kγi,xσ⁡\(i\)\)​z∑i=1kd⁡\(si,xσ⁡\(i\)\)\.u\_\{0\}\(X\)=\\sum\_\{\\sigma\\in S\_\{k\}\}\\sgn\(\\sigma\)\\left\(\\prod\_\{i=1\}^\{k\}\\gamma\_\{i,x\_\{\\sigma\(i\)\}\}\\right\)z^\{\\sum\_\{i=1\}^\{k\}d\(s\_\{i\},x\_\{\\sigma\(i\)\}\)\}\.\(7\)The exponent of each term is the cost of a matching fromC0C\_\{0\}toXX\. Different permutations give different coefficient monomials, even when their matching costs are equal\. Hence the least\-cost terms cannot cancel, and

ν⁡\(u0​\(X\)\)=D⁡\(C0,X\)=w0​\(X\)\.\\nu\(u\_\{0\}\(X\)\)=D\(C\_\{0\},X\)=w\_\{0\}\(X\)\.\(8\)In particular, everykkdistinct columns form a basis\.

For two servers, this construction reads

u0​\(x,y\)=γ1,x​γ2,y​zd⁡\(s1,x\)\+d⁡\(s2,y\)−γ1,y​γ2,x​zd⁡\(s1,y\)\+d⁡\(s2,x\)\.u\_\{0\}\(x,y\)=\\gamma\_\{1,x\}\\gamma\_\{2,y\}z^\{d\(s\_\{1\},x\)\+d\(s\_\{2\},y\)\}\-\\gamma\_\{1,y\}\\gamma\_\{2,x\}z^\{d\(s\_\{1\},y\)\+d\(s\_\{2\},x\)\}\.The two possible assignments have opposite signs\. If their costs tie, their coefficients still differ, so the minimum cost survives\. Using independent symbols rather than unit coefficients is essential for this simple argument\.

### 2\.3A request as a row replacement

We now maintain columnsqx∈𝕂kq\_\{x\}\\in\\mathbb\{K\}^\{k\}for which

u⁡\(X\):=det\(qx1,…,qxk\),ν⁡\(u⁡\(X\)\)=w⁡\(X\)u\(X\):=\\det\(q\_\{x\_\{1\}\},\\ldots,q\_\{x\_\{k\}\}\),\\qquad\\nu\(u\(X\)\)=w\(X\)\(9\)for every ordered configuration of distinct labels\. Exchanging two labels changes the sign ofu⁡\(X\)u\(X\), but leaves its valuation unchanged, as required for an unordered configuration\.

Assumek≥2k\\geq 2and a request arrives atrr\. The vectorqrq\_\{r\}is nonzero, since it belongs to a basis ofkkdistinct columns\. We first change coordinates so thatqr=e1q\_\{r\}=e\_\{1\}, while preserving every determinant exactly\.

###### Lemma 2\.2\(Determinant\-preserving normalization\)\.

For every nonzerov∈𝕂kv\\in\\mathbb\{K\}^\{k\}, withk≥2k\\geq 2, there is an invertible matrixBBsatisfyingB​v=e1Bv=e\_\{1\}anddetB=1\\det B=1\.

###### Proof\.

Gaussian elimination gives an invertible matrixTTwithT​v=e1Tv=e\_\{1\}\. Writec=detT≠0c=\\det T\\neq 0\. Multiply the second row ofTTbyc−1c^\{\-1\}\. The resulting matrixBBhas determinant one, and still sendsvvtoe1e\_\{1\}, whose second coordinate is zero\. ∎

Apply this matrix to every old column\. SincedetB=1\\det B=1, everykk\-column determinant is unchanged\. We continue to call the transformed columnsqxq\_\{x\}\. The matrixBBis chosen using only the old columns and therefore introduces no fresh coefficient variables\.

Writeqx=\(ax,q^x\)q\_\{x\}=\(a\_\{x\},\\widehat\{q\}\_\{x\}\), withax∈𝕂a\_\{x\}\\in\\mathbb\{K\}andq^x∈𝕂k−1\\widehat\{q\}\_\{x\}\\in\\mathbb\{K\}^\{k\-1\}\. In these coordinates,qr=\(1,0\)q\_\{r\}=\(1,0\)\. For request numbertt, set

δr=1,δx=ξt,xzd⁡\(r,x\)\(x≠r\),\\delta\_\{r\}=1,\\qquad\\delta\_\{x\}=\\xi\_\{t,x\}z^\{d\(r,x\)\}\\quad\(x\\neq r\),\(10\)and replace the columns by

qx′=\(δx,q^x\)\.q^\{\\prime\}\_\{x\}=\(\\delta\_\{x\},\\widehat\{q\}\_\{x\}\)\.\(11\)Equivalently, replace the first row of the entire column matrix by\(δx\)x∈M\(\\delta\_\{x\}\)\_\{x\\in M\}and leave the other rows unchanged\. Notice thatν⁡\(δx\)=d⁡\(r,x\)\\nu\(\\delta\_\{x\}\)=d\(r,x\)for everyxx\.

###### Lemma 2\.3\(Exact lifted recurrence\)\.

The new columns satisfyν⁡\(det\(qx1′,…,qxk′\)\)=w′​\(X\)\\nu\(\\det\(q^\{\\prime\}\_\{x\_\{1\}\},\\ldots,q^\{\\prime\}\_\{x\_\{k\}\}\)\)=w^\{\\prime\}\(X\)for every configurationXX\.

###### Proof\.

Expand the new determinant along its first row\. The signed minor accompanyingδxi\\delta\_\{x\_\{i\}\}is the determinant of the old columns with columniireplaced bye1=qre\_\{1\}=q\_\{r\}\. Indeed, expanding that replacement determinant along itse1e\_\{1\}column gives the same signed minor\. Thus

u′​\(x1,…,xk\)=∑i=1kδxi​u​\(x1,…,xi−1,r,xi\+1,…,xk\)\.u^\{\\prime\}\(x\_\{1\},\\ldots,x\_\{k\}\)=\\sum\_\{i=1\}^\{k\}\\delta\_\{x\_\{i\}\}u\(x\_\{1\},\\ldots,x\_\{i\-1\},r,x\_\{i\+1\},\\ldots,x\_\{k\}\)\.\(12\)The first\-row signs are already included in the replacement determinants; no extra signs are missing from this formula\.

Ifr∈Xr\\in X, the summand replacingrritself isu⁡\(X\)u\(X\), becauseδr=1\\delta\_\{r\}=1\. Every other summand has two copies of the columnqrq\_\{r\}and is zero\. Henceu′​\(X\)=u​\(X\)u^\{\\prime\}\(X\)=u\(X\)exactly\.

Ifr∉Xr\\notin X, the factorsξt,xi\\xi\_\{t,x\_\{i\}\}are distinct fresh variables, and the old determinants contain none of them\. Lemma[2\.1](https://arxiv.org/html/2609.15979#S2.Thmtheorem1)gives

ν⁡\(u′​\(X\)\)=mini⁡\{d⁡\(r,xi\)\+ν⁡\(u⁡\(X−xi\+r\)\)\}=w′​\(X\),\\nu\(u^\{\\prime\}\(X\)\)=\\min\_\{i\}\\bigl\\\{d\(r,x\_\{i\}\)\+\\nu\(u\(X\-x\_\{i\}\+r\)\)\\bigr\\\}=w^\{\\prime\}\(X\),where the last equality is \([2](https://arxiv.org/html/2609.15979#S1.E2)\)\. This proves the invariant after the request\. ∎

After the request column becomese1e\_\{1\}, determinants containing that column depend only on the other columns’ lastk−1k\-1coordinates\. The row replacement combines exactly those determinants, with the appropriate costs for moving from the request to the final locations\. Alternation eliminates configurations in which the request would occur twice\.

For example, with two servers the old columns have the formqx=\(ax,bx\)q\_\{x\}=\(a\_\{x\},b\_\{x\}\)andqr=\(1,0\)q\_\{r\}=\(1,0\)\. The new two\-column determinant is

det\(qx′,qy′\)=δx​by−δy​bx=δx​det\(qr,qy\)\+δy​det\(qx,qr\)\.\\det\(q^\{\\prime\}\_\{x\},q^\{\\prime\}\_\{y\}\)=\\delta\_\{x\}b\_\{y\}\-\\delta\_\{y\}b\_\{x\}=\\delta\_\{x\}\\det\(q\_\{r\},q\_\{y\}\)\+\\delta\_\{y\}\\det\(q\_\{x\},q\_\{r\}\)\.This is the two\-term work function recurrence before taking valuations\.

###### Theorem 2\.4\(Maintained algebraic state\)\.

For every finite request sequence, the initialization \([6](https://arxiv.org/html/2609.15979#S2.E6)\) and the determinant\-preserving normalization followed by \([11](https://arxiv.org/html/2609.15979#S2.E11)\) produce ak×nk\\times nmatrix whosekk\-column determinants have valuations exactly equal to the corresponding work function values at every time\.

###### Proof\.

The initialization is \([8](https://arxiv.org/html/2609.15979#S2.E8)\); preservation is Lemma[2\.3](https://arxiv.org/html/2609.15979#S2.Thmtheorem3)\. All coordinate operations before timettuse only coefficient variables from earlier times, so the required freshness holds inductively\. Although individual matrix entries may become rational functions, the determinants satisfy the exact recurrence \([12](https://arxiv.org/html/2609.15979#S2.E12)\); in particular, their dependence on the coefficient variables is controlled by this recurrence\. ∎

## 3Quadratic products and their determinants

We next explain the space in which the potential lives\. This construction uses ordinary polynomials in coordinate symbols; it is separate from the formal cost variablezz\.

### 3\.1The symmetric square in coordinates

Identify a vectora=\(a1,…,ak\)∈𝕂ka=\(a\_\{1\},\\ldots,a\_\{k\}\)\\in\\mathbb\{K\}^\{k\}with the linear polynomiala1​e1\+⋯\+ak​eka\_\{1\}e\_\{1\}\+\\cdots\+a\_\{k\}e\_\{k\}, wheree1,…,eke\_\{1\},\\ldots,e\_\{k\}are commuting formal symbols\. For vectorsa,ba,b, their producta​babis the usual product of these polynomials\. It is a homogeneous polynomial of degree two\. Its coordinate atei2e\_\{i\}^\{2\}isai​bia\_\{i\}b\_\{i\}, and its coordinate atei​eje\_\{i\}e\_\{j\}, fori<ji<j, isai​bj\+aj​bia\_\{i\}b\_\{j\}\+a\_\{j\}b\_\{i\}\.

The vector space of these quadratic polynomials is denotedSym2⁡𝕂k\\Sym^\{2\}\\mathbb\{K\}^\{k\}\. Its dimension isN=k⁡\(k\+1\)/2N=k\(k\+1\)/2, and its monomial basis, in lexicographic order, is

\(ei​ej\)1≤i≤j≤k\.\(e\_\{i\}e\_\{j\}\)\_\{1\\leq i\\leq j\\leq k\}\.\(13\)The notation names this concrete vector space; no tensor\-product construction is required\. Fork=2k=2, the product is simply the three\-dimensional column

a​b=\(a1​b1a1​b2\+a2​b1a2​b2\)\.ab=\\begin\{pmatrix\}a\_\{1\}b\_\{1\}\\\\ a\_\{1\}b\_\{2\}\+a\_\{2\}b\_\{1\}\\\\ a\_\{2\}b\_\{2\}\\end\{pmatrix\}\.Fork=3k=3, the six coordinate symbols aree12,e1​e2,e1​e3,e22,e2​e3,e32e\_\{1\}^\{2\},e\_\{1\}e\_\{2\},e\_\{1\}e\_\{3\},e\_\{2\}^\{2\},e\_\{2\}e\_\{3\},e\_\{3\}^\{2\}\.

An invertible matrixAAacts on linear polynomials by sending each basis vectoreie\_\{i\}toA​eiAe\_\{i\}\. Substituting these linear polynomials into a quadratic polynomial gives an invertible linear map on the quadratic space, denotedSym2⁡A\\Sym^\{2\}A\. By construction,

\(Sym2⁡A\)​\(a​b\)=\(A​a\)​\(A​b\)\.\(\\Sym^\{2\}A\)\(ab\)=\(Aa\)\(Ab\)\.Consequently, ifa1,…,aka\_\{1\},\\ldots,a\_\{k\}are a basis of𝕂k\\mathbb\{K\}^\{k\}, theirNNproductsai​aja\_\{i\}a\_\{j\},i≤ji\\leq j, are a basis of the quadratic space\.

The following lemma is a well\-known result that goes back to\[[57](https://arxiv.org/html/2609.15979#bib.bib62)\], as it is reported in\[[54](https://arxiv.org/html/2609.15979#bib.bib61), pp\. 52\-53\]\. For completeness, we add its proof in Appendix[A](https://arxiv.org/html/2609.15979#A1.SSx2)\.

###### Lemma 3\.1\(Determinant of the symmetric square\)\.

For every invertiblek×kk\\times kmatrixAA,

det\(Sym2⁡A\)=\(detA\)k\+1\.\\det\(\\Sym^\{2\}A\)=\(\\det A\)^\{k\+1\}\.\(14\)

The exponentk\+1k\+1has a simple counting interpretation: a given basis vector occurs twice in its square and once in each of itsk−1k\-1mixed products\. This is why the quadratic space is suited to the\(k\+1\)\(k\+1\)coefficient in the extended\-cost bound\.

### 3\.2Minimum valuations of maximal minors

LetG=\[g1⋯gm\]G=\[g\_\{1\}\\ \\cdots\\ g\_\{m\}\]be a matrix whose columns span𝕂d\\mathbb\{K\}^\{d\}\. Define

μ⁡\(G\)=min1≤i1<⋯<id≤m⁡ν⁡\(det\(gi1,…,gid\)\)\.\\mu\(G\)=\\min\_\{1\\leq i\_\{1\}<\\cdots<i\_\{d\}\\leq m\}\\nu\(\\det\(g\_\{i\_\{1\}\},\\ldots,g\_\{i\_\{d\}\}\)\)\.\(15\)A dependent choice contributes\+∞\+\\infty\. Because the family spans, at least one choice is independent\. Column order affects only the determinant’s sign, which has valuation zero\.

###### Lemma 3\.2\(Rules for minor valuations\)\.

The following facts hold for spanning column families\.

1. 1\.IfAAis an invertibled×dd\\times dmatrix, thenμ⁡\(A​G\)=ν⁡\(detA\)\+μ⁡\(G\)\\mu\(AG\)=\\nu\(\\det A\)\+\\mu\(G\)\.
2. 2\.If every column of a spanning familyFFis a linear combination of columns ofGGwith coefficients of nonnegative valuation, thenμ⁡\(F\)≥μ⁡\(G\)\\mu\(F\)\\geq\\mu\(G\)\.
3. 3\.IfGGis block diagonal with blocksG1,…,GsG\_\{1\},\\ldots,G\_\{s\}, thenμ⁡\(G\)=∑j=1sμ⁡\(Gj\)\\mu\(G\)=\\sum\_\{j=1\}^\{s\}\\mu\(G\_\{j\}\)\.

###### Proof\.

For the first statement, every selected determinant is multiplied bydetA\\det A\. For the second, expand a determinant ofddcolumns ofFFmultilinearly in columns ofGG\. Each summand is a determinant ofddcolumns ofGG, multiplied byddcoefficients of total valuation at least zero\. Every summand therefore has valuation at leastμ⁡\(G\)\\mu\(G\), and so does their sum by \([5](https://arxiv.org/html/2609.15979#S2.E5)\)\.

For the third statement, letdjd\_\{j\}be the number of rows ofGjG\_\{j\}\. A nonzero full determinant must choose exactlydjd\_\{j\}columns from each block: choosing more makes those columns dependent, and choosing fewer leaves that block unspanned\. The determinant is then the product of the block determinants, and its valuation is the sum of their valuations\. Choosing a minimum determinant independently in every block attains the claimed sum\. ∎

We will also use block upper triangular matrices\. For a matrix\(U∗0W\)\\left\(\\begin\{smallmatrix\}U&\*\\\\ 0&W\\end\{smallmatrix\}\\right\)with square diagonal blocks, its determinant isdetU​detW\\det U\\det W, so the determinant valuation is the sum of the two block valuations\.

## 4The potential and its increase at a request

Fix any total order on the finite label setMM\. At each time define theN×\(n\+12\)N\\times\\binom\{n\+1\}\{2\}matrix𝒬\\mathcal\{Q\}, whereN=\(k\+12\)N=\\binom\{k\+1\}\{2\}, and potentialΨ\\Psiby

𝒬=\[z−d⁡\(x,y\)​qx​qy\]x≤y,Ψ=μ⁡\(𝒬\)\.\\mathcal\{Q\}=\[\\,z^\{\-d\(x,y\)\}q\_\{x\}q\_\{y\}\\,\]\_\{x\\leq y\},\\qquad\\Psi=\\mu\(\\mathcal\{Q\}\)\.\(16\)The columns are written in the monomial coordinates \([13](https://arxiv.org/html/2609.15979#S3.E13)\)\. This family spans: choose any configuration ofkkdistinct labels, whose columns form a basis by Theorem[2\.4](https://arxiv.org/html/2609.15979#S2.Thmtheorem4); their pairwise products form a basis of the quadratic space\. Multiplying those products by nonzero distance weights preserves their independence\.

Before processing a request, we apply the matrixBBfrom Lemma[2\.2](https://arxiv.org/html/2609.15979#S2.Thmtheorem2)to every column\. This replaces𝒬\\mathcal\{Q\}by\(Sym2⁡B\)​𝒬\(\\Sym^\{2\}B\)\\mathcal\{Q\}\. Lemmas[3\.1](https://arxiv.org/html/2609.15979#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2609.15979#S3.Thmtheorem2)show thatΨ\\Psiis unchanged, sincedetB=1\\det B=1\. Therefore we may analyze the request in coordinates whereqr=e1q\_\{r\}=e\_\{1\}\.

### 4\.1Three quantities associated with the request

Writeqx=\(ax,q^x\)q\_\{x\}=\(a\_\{x\},\\widehat\{q\}\_\{x\}\)and letπ:𝕂k→𝕂k−1\\pi:\\mathbb\{K\}^\{k\}\\to\\mathbb\{K\}^\{k\-1\}delete the first coordinate\. Define the weighted columns and their projection by

hx=z−d⁡\(r,x\)​qx,H=\[hx\]x∈M,H^=\[π​hx\]x∈M\.h\_\{x\}=z^\{\-d\(r,x\)\}q\_\{x\},\\qquad H=\[h\_\{x\}\]\_\{x\\in M\},\\qquad\\widehat\{H\}=\[\\pi h\_\{x\}\]\_\{x\\in M\}\.\(17\)Let𝒬^\\widehat\{\\mathcal\{Q\}\}be the bottom coordinate block of𝒬\\mathcal\{Q\}, consisting of the rowsei​eje\_\{i\}e\_\{j\}with2≤i≤j≤k2\\leq i\\leq j\\leq k:

𝒬^=\[z−d⁡\(x,y\)​q^x​q^y\]x≤y\.\\widehat\{\\mathcal\{Q\}\}=\[\\,z^\{\-d\(x,y\)\}\\widehat\{q\}\_\{x\}\\widehat\{q\}\_\{y\}\\,\]\_\{x\\leq y\}\.\(18\)Consider the three quantitiesμ⁡\(H\),μ⁡\(H^\)\\mu\(H\),\\mu\(\\widehat\{H\}\)andμ⁡\(𝒬^\)\\mu\(\\widehat\{\\mathcal\{Q\}\}\)\. The determinants defining these quantities have sizeskk,k−1k\-1, and\(k2\)=N−k\\binom\{k\}\{2\}=N\-k, respectively\. Each family spans its coordinate space:HHspans𝕂k\\mathbb\{K\}^\{k\}, its projection spans𝕂k−1\\mathbb\{K\}^\{k\-1\}, and products of a projected basis span the remaining quadratic coordinates\. All three quantities are therefore finite\.

We will prove

Ψ≤μ\(𝒬^\)\+μ\(H\),Ψ′≥μ\(𝒬^\)\+μ\(H^\),w′\(X\)−w\(X\)≤μ\(H^\)−μ\(H\)for allX\.\\Psi\\leq\\mu\(\\widehat\{\\mathcal\{Q\}\}\)\+\\mu\(H\),\\qquad\\Psi^\{\\prime\}\\geq\\mu\(\\widehat\{\\mathcal\{Q\}\}\)\+\\mu\(\\widehat\{H\}\),\\qquad w^\{\\prime\}\(X\)\-w\(X\)\\leq\\mu\(\\widehat\{H\}\)\-\\mu\(H\)\\quad\\text\{for all \}X\.\(19\)The first inequality selects one useful minor of the old matrix𝒬\\mathcal\{Q\}\. The second bounds every minor of the new matrix𝒬′\\mathcal\{Q\}^\{\\prime\}\. The third relates the extended cost to the difference between these two potential bounds\.

### 4\.2A useful minor of the old quadratic matrix

###### Lemma 4\.1\.

The old potential before the request satisfiesΨ≤μ⁡\(𝒬^\)\+μ⁡\(H\)\\Psi\\leq\\mu\(\\widehat\{\\mathcal\{Q\}\}\)\+\\mu\(H\)\.

###### Proof\.

The firstkkquadratic coordinates are

e12,e1​e2,…,e1​ek\.e\_\{1\}^\{2\},e\_\{1\}e\_\{2\},\\ldots,e\_\{1\}e\_\{k\}\.Multiplying a vectorh∈𝕂kh\\in\\mathbb\{K\}^\{k\}bye1e\_\{1\}puts itskkcoordinates into these rows and puts zeros into every remaining quadratic row\. Becauseqr=e1q\_\{r\}=e\_\{1\}, the columns

e1​hx=z−d⁡\(r,x\)​qr​qxe\_\{1\}h\_\{x\}=z^\{\-d\(r,x\)\}q\_\{r\}q\_\{x\}are actual columns of𝒬\\mathcal\{Q\}, namely its pairs\(r,x\)\(r,x\)\.

Choosekkcolumns ofHHattainingμ⁡\(H\)\\mu\(H\)and take the correspondingkkcolumnse1​hxe\_\{1\}h\_\{x\}of𝒬\\mathcal\{Q\}\. Their firstkkrows give the selectedHHminor and their bottom rows are zero\. Next chooseN−kN\-kcolumns of𝒬\\mathcal\{Q\}whose bottom blocks attainμ⁡\(𝒬^\)\\mu\(\\widehat\{\\mathcal\{Q\}\}\)in𝒬^\\widehat\{\\mathcal\{Q\}\}\. They do not include any column of the first selected columns, since those have zero bottom blocks and could not occur in a nonzero bottom\-block determinant\.

Together theseNNcolumns form a square matrix of the form

\(H∗∗0Q^∗\),\\begin\{pmatrix\}H\_\{\*\}&\*\\\\ 0&\\widehat\{Q\}\_\{\*\}\\end\{pmatrix\},whereν⁡\(detH∗\)=μ⁡\(H\)\\nu\(\\det H\_\{\*\}\)=\\mu\(H\)andν⁡\(detQ^∗\)=μ⁡\(𝒬^\)\\nu\(\\det\\widehat\{Q\}\_\{\*\}\)=\\mu\(\\widehat\{\\mathcal\{Q\}\}\)\. The determinant has valuationμ⁡\(H\)\+μ⁡\(𝒬^\)\\mu\(H\)\+\\mu\(\\widehat\{\\mathcal\{Q\}\}\)\. SinceΨ\\Psiis the minimum over all maximal minors of𝒬\\mathcal\{Q\}, it is at most this value\. ∎

### 4\.3A bound on every minor of the new quadratic matrix

###### Lemma 4\.2\.

The new potential after the request satisfiesΨ′≥μ⁡\(𝒬^\)\+μ⁡\(H^\)\\Psi^\{\\prime\}\\geq\\mu\(\\widehat\{\\mathcal\{Q\}\}\)\+\\mu\(\\widehat\{H\}\)\.

###### Proof\.

Viewq^x\\widehat\{q\}\_\{x\}as a linear polynomial ine2,…,eke\_\{2\},\\ldots,e\_\{k\}\. The update isqx′=δx​e1\+q^xq^\{\\prime\}\_\{x\}=\\delta\_\{x\}e\_\{1\}\+\\widehat\{q\}\_\{x\}\. Expanding one new quadratic column gives

z−d⁡\(x,y\)​qx′​qy′=\\displaystyle z^\{\-d\(x,y\)\}q^\{\\prime\}\_\{x\}q^\{\\prime\}\_\{y\}=\{\}z−d⁡\(x,y\)​δx​δy​e12\\displaystyle z^\{\-d\(x,y\)\}\\delta\_\{x\}\\delta\_\{y\}e\_\{1\}^\{2\}\+e1​z−d⁡\(x,y\)​\(δx​q^y\+δy​q^x\)\\displaystyle\+e\_\{1\}z^\{\-d\(x,y\)\}\(\\delta\_\{x\}\\widehat\{q\}\_\{y\}\+\\delta\_\{y\}\\widehat\{q\}\_\{x\}\)\+z−d⁡\(x,y\)​q^x​q^y\.\\displaystyle\+z^\{\-d\(x,y\)\}\\widehat\{q\}\_\{x\}\\widehat\{q\}\_\{y\}\.\(20\)The expressions in these three lines occupy disjoint coordinate blocks: the single rowe12e\_\{1\}^\{2\}; thek−1k\-1rowse1​eje\_\{1\}e\_\{j\},j≥2j\\geq 2; and theN−kN\-krows not involvinge1e\_\{1\}\.

Compare the new columns to the following family, supported separately on these three blocks:

\{e12\}∪\{e1​π​hx:x∈M\}∪\{z−d⁡\(x,y\)​q^x​q^y:x≤y\}\.\\\{e\_\{1\}^\{2\}\\\}\\;\\cup\\;\\\{e\_\{1\}\\pi h\_\{x\}:x\\in M\\\}\\;\\cup\\;\\\{z^\{\-d\(x,y\)\}\\widehat\{q\}\_\{x\}\\widehat\{q\}\_\{y\}:x\\leq y\\\}\.\(21\)Its minimum full\-minor valuation is0\+μ⁡\(H^\)\+μ⁡\(𝒬^\)0\+\\mu\(\\widehat\{H\}\)\+\\mu\(\\widehat\{\\mathcal\{Q\}\}\), by the block rule of Lemma[3\.2](https://arxiv.org/html/2609.15979#S3.Thmtheorem2)\. We show that every column in \([20](https://arxiv.org/html/2609.15979#S4.E20)\) is a linear combination of this family with coefficient valuations at least zero\.

The coefficient ofe12e\_\{1\}^\{2\}has valuation

ν⁡\(z−d⁡\(x,y\)​δx​δy\)=d⁡\(r,x\)\+d⁡\(r,y\)−d⁡\(x,y\)≥0\.\\nu\(z^\{\-d\(x,y\)\}\\delta\_\{x\}\\delta\_\{y\}\)=d\(r,x\)\+d\(r,y\)\-d\(x,y\)\\geq 0\.\(22\)For a mixed term, useπ​hy=z−d⁡\(r,y\)​q^y\\pi h\_\{y\}=z^\{\-d\(r,y\)\}\\widehat\{q\}\_\{y\}to write

e1​z−d⁡\(x,y\)​δx​q^y=\(zd⁡\(r,y\)−d⁡\(x,y\)​δx\)​e1​π​hy\.e\_\{1\}z^\{\-d\(x,y\)\}\\delta\_\{x\}\\widehat\{q\}\_\{y\}=\\bigl\(z^\{d\(r,y\)\-d\(x,y\)\}\\delta\_\{x\}\\bigr\)e\_\{1\}\\pi h\_\{y\}\.The coefficient in parentheses has non\-negative valuation\. The other mixed term in \([20](https://arxiv.org/html/2609.15979#S4.E20)\) has the analogous expression withxxandyyinterchanged\. Finally, the last line of \([20](https://arxiv.org/html/2609.15979#S4.E20)\) is already a column of the third family, with coefficient one\.

The second rule of Lemma[3\.2](https://arxiv.org/html/2609.15979#S3.Thmtheorem2)now shows that every maximal minor of𝒬′\\mathcal\{Q\}^\{\\prime\}has valuation at leastμ⁡\(𝒬^\)\+μ⁡\(H^\)\\mu\(\\widehat\{\\mathcal\{Q\}\}\)\+\\mu\(\\widehat\{H\}\)\. Taking their minimum proves the assertion\. ∎

Combining the preceding two lemmas gives

Ψ′−Ψ≥μ⁡\(H^\)−μ⁡\(H\)\.\\Psi^\{\\prime\}\-\\Psi\\geq\\mu\(\\widehat\{H\}\)\-\\mu\(H\)\.\(23\)

### 4\.4Why the potential change pays the extended cost

###### Lemma 4\.3\.

For every configurationXX,w′​\(X\)−w⁡\(X\)≤μ⁡\(H^\)−μ⁡\(H\)w^\{\\prime\}\(X\)\-w\(X\)\\leq\\mu\(\\widehat\{H\}\)\-\\mu\(H\)\.

###### Proof\.

First supposer∉Xr\\notin X\. The old columnsqx1,…,qxkq\_\{x\_\{1\}\},\\ldots,q\_\{x\_\{k\}\}are a basis, so write the request column in this basis:

e1=qr=∑i=1kci​qxi\.e\_\{1\}=q\_\{r\}=\\sum\_\{i=1\}^\{k\}c\_\{i\}q\_\{x\_\{i\}\}\.\(24\)Replacing theiith column of this basis bye1e\_\{1\}multiplies its determinant bycic\_\{i\}: substitute \([24](https://arxiv.org/html/2609.15979#S4.E24)\) and use multilinearity, observing that every summand exceptiihas a repeated column and vanishes\. This is Cramer’s rule, and it gives

ci=u⁡\(X−xi\+r\)u⁡\(X\),ν⁡\(ci\)=w⁡\(X−xi\+r\)−w⁡\(X\)\.c\_\{i\}=\\frac\{u\(X\-x\_\{i\}\+r\)\}\{u\(X\)\},\\qquad\\nu\(c\_\{i\}\)=w\(X\-x\_\{i\}\+r\)\-w\(X\)\.By the work function recurrence, the increase atXXis therefore

m:=w′​\(X\)−w⁡\(X\)=mini⁡\{ν⁡\(ci\)\+d⁡\(r,xi\)\}\.m:=w^\{\\prime\}\(X\)\-w\(X\)=\\min\_\{i\}\\bigl\\\{\\nu\(c\_\{i\}\)\+d\(r,x\_\{i\}\)\\bigr\\\}\.\(25\)
Consider anyk−1k\-1columnsπ​hy1,…,π​hyk−1\\pi h\_\{y\_\{1\}\},\\ldots,\\pi h\_\{y\_\{k\-1\}\}ofH^\\widehat\{H\}\. We have

det\(π​hy1,…,π​hyk−1\)\\displaystyle\\det\(\\pi h\_\{y\_\{1\}\},\\ldots,\\pi h\_\{y\_\{k\-1\}\}\)=det\(e1,hy1,…,hyk−1\)\\displaystyle=\\det\(e\_\{1\},h\_\{y\_\{1\}\},\\ldots,h\_\{y\_\{k\-1\}\}\)=∑i=1kci​zd⁡\(r,xi\)​det\(hxi,hy1,…,hyk−1\)\.\\displaystyle=\\sum\_\{i=1\}^\{k\}c\_\{i\}z^\{d\(r,x\_\{i\}\)\}\\det\(h\_\{x\_\{i\}\},h\_\{y\_\{1\}\},\\ldots,h\_\{y\_\{k\-1\}\}\)\.\(26\)The first equality is expansion along the first column; the second substitutes \([24](https://arxiv.org/html/2609.15979#S4.E24)\) and usesqxi=zd⁡\(r,xi\)​hxiq\_\{x\_\{i\}\}=z^\{d\(r,x\_\{i\}\)\}h\_\{x\_\{i\}\}\.

Every determinant in the final line is either zero or a maximal minor ofHH, up to a column ordering\. Its valuation is at leastμ⁡\(H\)\\mu\(H\)\. Equation \([25](https://arxiv.org/html/2609.15979#S4.E25)\) bounds the valuation of each coefficientci​zd⁡\(r,xi\)c\_\{i\}z^\{d\(r,x\_\{i\}\)\}below bymm\. Hence every summand has valuation at leastμ⁡\(H\)\+m\\mu\(H\)\+m, and so does their sum\. Minimizing the left side over the projected columns provesμ⁡\(H^\)≥μ⁡\(H\)\+m\\mu\(\\widehat\{H\}\)\\geq\\mu\(H\)\+m\.

For the caser∈Xr\\in X, the work function increase is zero\. Independently of the choice ofXX, we haveμ⁡\(H^\)≥μ⁡\(H\)\\mu\(\\widehat\{H\}\)\\geq\\mu\(H\): sincehr=e1h\_\{r\}=e\_\{1\}, each determinant definingμ⁡\(H^\)\\mu\(\\widehat\{H\}\)is, by the first equality of \([26](https://arxiv.org/html/2609.15979#S4.E26)\), already a determinant ofkkcolumns ofHH\. Its valuation is therefore at leastμ⁡\(H\)\\mu\(H\)\. This completes the remaining case\. ∎

###### Corollary 4\.4\(The potential pays every request\)\.

For each timett,

ExtCostt≤Ψt−Ψt−1\.\\mathrm\{ExtCost\}\_\{t\}\\leq\\Psi\_\{t\}\-\\Psi\_\{t\-1\}\.

###### Proof\.

Immediate from Lemma[4\.3](https://arxiv.org/html/2609.15979#S4.Thmtheorem3)and \([23](https://arxiv.org/html/2609.15979#S4.E23)\)\. ∎

## 5Initial and final potential values

We now prove bounds on the initial and terminal values of the potential function\.

###### Lemma 5\.1\(Terminal bound\)\.

At every time and for every configurationXX, we have

Ψ≤\(k\+1\)​w​\(X\)−cl⁡\(X\)\.\\Psi\\leq\(k\+1\)w\(X\)\-\\cl\(X\)\.\(27\)

###### Proof\.

LetAAbe thek×kk\\times kmatrix with columnsqx1,…,qxkq\_\{x\_\{1\}\},\\ldots,q\_\{x\_\{k\}\}\. Select from𝒬\\mathcal\{Q\}theNNcolumns

z−d⁡\(xi,xj\)​qxi​qxj,1≤i≤j≤k\.z^\{\-d\(x\_\{i\},x\_\{j\}\)\}q\_\{x\_\{i\}\}q\_\{x\_\{j\}\},\\qquad 1\\leq i\\leq j\\leq k\.Without the scalar weights, their matrix isSym2⁡A\\Sym^\{2\}A, since its columns are the images of the coordinate monomialsei​eje\_\{i\}e\_\{j\}\. The determinant is nonzero and, by Lemma[3\.1](https://arxiv.org/html/2609.15979#S3.Thmtheorem1), its valuation is\(k\+1\)​ν​\(detA\)=\(k\+1\)​w​\(X\)\(k\+1\)\\nu\(\\det A\)=\(k\+1\)w\(X\)\. The scalar weights subtract

∑i≤jd⁡\(xi,xj\)=∑i<jd⁡\(xi,xj\)=cl⁡\(X\)\\sum\_\{i\\leq j\}d\(x\_\{i\},x\_\{j\}\)=\\sum\_\{i<j\}d\(x\_\{i\},x\_\{j\}\)=\\cl\(X\)from the determinant valuation; diagonal distances are zero\. This gives one maximal minor of𝒬\\mathcal\{Q\}with the claimed valuation, andΨ\\Psiis the minimum over all such minors\. ∎

###### Lemma 5\.2\(Initial value\)\.

The initialization \([6](https://arxiv.org/html/2609.15979#S2.E6)\) satisfiesΨ0=−cl⁡\(C0\)\\Psi\_\{0\}=\-\\cl\(C\_\{0\}\)\.

###### Proof\.

The terminal bound applied at time zero withX=C0X=C\_\{0\}givesΨ0≤−cl⁡\(C0\)\\Psi\_\{0\}\\leq\-\\cl\(C\_\{0\}\), sincew0​\(C0\)=0w\_\{0\}\(C\_\{0\}\)=0\.

For the reverse inequality, fix a rowei​eje\_\{i\}e\_\{j\}of the initial quadratic matrix and a column indexed by\(x,y\)\(x,y\)\. Ifi<ji<j, its entry is

z−d⁡\(x,y\)​\(\(qx\)i​\(qy\)j\+\(qx\)j​\(qy\)i\)\.z^\{\-d\(x,y\)\}\\bigl\(\(q\_\{x\}\)\_\{i\}\(q\_\{y\}\)\_\{j\}\+\(q\_\{x\}\)\_\{j\}\(q\_\{y\}\)\_\{i\}\\bigr\)\.The valuation of the first summand is

d⁡\(si,x\)\+d⁡\(sj,y\)−d⁡\(x,y\)≥−d⁡\(si,sj\)d\(s\_\{i\},x\)\+d\(s\_\{j\},y\)\-d\(x,y\)\\geq\-d\(s\_\{i\},s\_\{j\}\)by triangle inequality along the pathx,si,sj,yx,s\_\{i\},s\_\{j\},y\. The second summand has the same lower bound\. Thus the whole entry has valuation at least−d⁡\(si,sj\)\-d\(s\_\{i\},s\_\{j\}\)\.

Ifi=ji=j, the entry has just one product\. Its valuation isd⁡\(si,x\)\+d⁡\(si,y\)−d⁡\(x,y\)≥0=−d⁡\(si,si\)d\(s\_\{i\},x\)\+d\(s\_\{i\},y\)\-d\(x,y\)\\geq 0=\-d\(s\_\{i\},s\_\{i\}\)\. Therefore every entry in rowei​eje\_\{i\}e\_\{j\}has valuation at least−d⁡\(si,sj\)\-d\(s\_\{i\},s\_\{j\}\), including diagonal rows\.

Expand anyN×NN\\times Nminor by permutations\. Each product chooses one entry from each row and hence has valuation at least

−∑i≤jd\(si,sj\)=−cl\(C0\)\.\-\\sum\_\{i\\leq j\}d\(s\_\{i\},s\_\{j\}\)=\-\\cl\(C\_\{0\}\)\.The valuation of the sum cannot be smaller\. This bounds every maximal minor from below, givingΨ0≥−cl⁡\(C0\)\\Psi\_\{0\}\\geq\-\\cl\(C\_\{0\}\)\. ∎

###### Theorem 5\.3\.

LetXTX\_\{T\}be a configuration minimizingwTw\_\{T\}\. Then

∑t=1TExtCostt\\displaystyle\\sum\_\{t=1\}^\{T\}\\mathrm\{ExtCost\}\_\{t\}≤\(k\+1\)​wT​\(XT\)\+cl⁡\(C0\)−cl⁡\(XT\),\\displaystyle\\leq\(k\+1\)w\_\{T\}\(X\_\{T\}\)\+\\cl\(C\_\{0\}\)\-\\cl\(X\_\{T\}\),\(28\)WFAC0⁡\(r1,…,rT\)\\displaystyle\\WFA\_\{C\_\{0\}\}\(r\_\{1\},\\ldots,r\_\{T\}\)≤k​wT​\(XT\)\+cl⁡\(C0\)−cl⁡\(XT\)\.\\displaystyle\\leq k\\,w\_\{T\}\(X\_\{T\}\)\+\\cl\(C\_\{0\}\)\-\\cl\(X\_\{T\}\)\.\(29\)

###### Proof\.

Sum Corollary[4\.4](https://arxiv.org/html/2609.15979#S4.Thmtheorem4)over the requests\. The potential telescopes, and the endpoint lemmas give

∑tExtCostt≤ΨT−Ψ0≤\(k\+1\)​wT​\(XT\)−cl⁡\(XT\)\+cl⁡\(C0\)\.\\sum\_\{t\}\\mathrm\{ExtCost\}\_\{t\}\\leq\\Psi\_\{T\}\-\\Psi\_\{0\}\\leq\(k\+1\)w\_\{T\}\(X\_\{T\}\)\-\\cl\(X\_\{T\}\)\+\\cl\(C\_\{0\}\)\.SubtractwT​\(CT\)≥wT​\(XT\)w\_\{T\}\(C\_\{T\}\)\\geq w\_\{T\}\(X\_\{T\}\)from the accounting inequality in Lemma[1\.1](https://arxiv.org/html/2609.15979#S1.Thmtheorem1)to obtain \([29](https://arxiv.org/html/2609.15979#S5.E29)\)\. ∎

## Acknowledgments

This work began with a potential function designed by the authors that proves the previously unknown case ofk=3k=3servers on arbitrary metrics\. Our initial proof for three servers showed the correctness of this potential function by establishing infeasibility of a large family of linear programs; this proof was obtained without AI assistance\. Through discussions with ChatGPT 5\.5 Pro and Gemini 3\.1 Pro, we gained a deeper understanding of the potential\. These discussions led to a more symmetric reformulation of the potential, again designed by the authors, and an alternative proof fork=3k=3\. Based on this, ChatGPT 6 Astra subsequently derived an algebraic proof of correctness for anykk\. The proof in this paper is an adaptation thereof using an explicit column representation of work functions, which provides a more natural algebraic representation\. The authors supplied this representation to ChatGPT 6 Astra, which adapted the previous proof and assisted with drafting some sections of this paper\. The authors subsequently revised those drafts\.

Verification of some ideas of generalization fromk=3k=3tok=4k=4has used the University of Oxford Advanced Research Computing \(ARC\) facility\[[56](https://arxiv.org/html/2609.15979#bib.bib49)\]\.

Christian Coester is funded by the European Union \(ERC, CCOO, 101165139\)\. Views and opinions expressed are however those of the author\(s\) only and do not necessarily reflect those of the European Union or the European Research Council\. Neither the European Union nor the granting authority can be held responsible for them\. Marek Zbysiński is funded by EPSRC grant EP/Z534870/1\.

> The second author, Elias Koutsoupias, dedicates this work to his constant friends Amos Fiat, Anna Karlin, and Christos Papadimitriou\.

## References

- \[AHK\+02\]E\. J\. Anderson, K\. Hildrum, A\. R\. Karlin, A\. Rasala, and M\. E\. Saks\(2002\)On list update and work function algorithms\.Theor\. Comput\. Sci\.287\(2\),pp\. 393–418\.External Links:[Document](https://dx.doi.org/10.1016/S0304-3975%2801%2900253-5)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px2.p1.1)\.
- \[AGT\+21\]C\. J\. Argue, A\. Gupta, Z\. Tang, and G\. Guruganesh\(2021\)Chasing convex bodies with linear competitive ratio\.J\. ACM68\(5\),pp\. 32:1–32:10\.External Links:[Document](https://dx.doi.org/10.1145/3450349)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px2.p1.1)\.
- \[BBM\+15\]N\. Bansal, N\. Buchbinder, A\. Madry, and J\. Naor\(2015\)A polylogarithmic\-competitive algorithm for the*k*\-server problem\.J\. ACM62\(5\),pp\. 40:1–40:49\.External Links:[Document](https://dx.doi.org/10.1145/2783434)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px4.p1.1)\.
- \[BBN10\]N\. Bansal, N\. Buchbinder, and J\. Naor\(2010\)Towards the randomized k\-server conjecture: A primal\-dual approach\.InProceedings of the Twenty\-First Annual ACM\-SIAM Symposium on Discrete Algorithms, SODA,pp\. 40–55\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611973075.5)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p1.1)\.
- \[BBN12\]N\. Bansal, N\. Buchbinder, and J\. Naor\(2012\)A primal\-dual randomized algorithm for weighted paging\.J\. ACM59\(4\),pp\. 19:1–19:24\.External Links:[Document](https://dx.doi.org/10.1145/2339123.2339126)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px4.p1.1)\.
- \[BEK\+23\]N\. Bansal, M\. Eliás, G\. Koumoutsos, and J\. Nederlof\(2023\)Competitive algorithms for generalized*k*\-server in uniform metrics\.ACM Trans\. Algorithms19\(1\),pp\. 8:1–8:15\.External Links:[Document](https://dx.doi.org/10.1145/3568677)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[BEK17\]N\. Bansal, M\. Eliás, and G\. Koumoutsos\(2017\)Weighted k\-server bounds via combinatorial dichotomies\.In58th IEEE Annual Symposium on Foundations of Computer Science, FOCS,pp\. 493–504\.External Links:[Document](https://dx.doi.org/10.1109/FOCS.2017.52)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[BG00\]Y\. Bartal and E\. Grove\(2000\)The harmonic*k*\-server algorithm is competitive\.J\. ACM47\(1\),pp\. 1–15\.External Links:[Document](https://dx.doi.org/10.1145/331605.331606)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p2.1)\.
- \[BK04\]Y\. Bartal and E\. Koutsoupias\(2004\)On the competitive ratio of the work function algorithm for the k\-server problem\.Theor\. Comput\. Sci\.324\(2\-3\),pp\. 337–345\.External Links:[Document](https://dx.doi.org/10.1016/J.TCS.2004.06.001)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p4.1)\.
- \[BCL02\]W\. W\. Bein, M\. Chrobak, and L\. L\. Larmore\(2002\)The 3\-server problem in the plane\.Theor\. Comput\. Sci\.289\(1\),pp\. 335–354\.External Links:[Document](https://dx.doi.org/10.1016/S0304-3975%2801%2900305-X)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p4.1)\.
- \[BBK\+94\]S\. Ben\-David, A\. Borodin, R\. M\. Karp, G\. Tardos, and A\. Wigderson\(1994\)On the power of randomization in on\-line algorithms\.Algorithmica11\(1\),pp\. 2–14\.External Links:[Document](https://dx.doi.org/10.1007/BF01294260)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p2.1)\.
- \[BBC\+20\]M\. Bienkowski, J\. Byrka, C\. Coester, and L\. Jez\(2020\)Unbounded lower bound for k\-server against weak adversaries\.InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC,pp\. 1165–1169\.External Links:[Document](https://dx.doi.org/10.1145/3357713.3384306)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[BMC26\]A\. Bijoy, A\. Mondal, and A\. Chiplunkar\(2026\)Weighted k\-server admits an exponentially competitive algorithm\.InProceedings of the 2026 Annual ACM\-SIAM Symposium on Discrete Algorithms, SODA,pp\. 4188–4208\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611978971.154)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[BE98\]A\. Borodin and R\. El\-Yaniv\(1998\)Online computation and competitive analysis\.Cambridge University Press\.Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px2.p1.1)\.
- \[BLS92\]A\. Borodin, N\. Linial, and M\. E\. Saks\(1992\)An optimal on\-line algorithm for metrical task system\.J\. ACM39\(4\),pp\. 745–763\.External Links:[Link](https://doi.org/10.1145/146585.146588),[Document](https://dx.doi.org/10.1145/146585.146588)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[BBA26\]K\. Brilliantov, E\. Bamas, and E\. Abbé\(2026\)K\-server\-bench: automating potential discovery for the k\-server conjecture\.arXiv preprint\.External Links:[Document](https://dx.doi.org/10.48550/ARXIV.2604.07240)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p1.1)\.
- \[BCR23\]S\. Bubeck, C\. Coester, and Y\. Rabani\(2023\)The randomized k\-server conjecture is false\!\.InProceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC,pp\. 581–594\.External Links:[Document](https://dx.doi.org/10.1145/3564246.3585132)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1),[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px4.p1.1)\.
- \[BCR25\]S\. Bubeck, C\. Coester, and Y\. Rabani\(2025\)Shortest paths without a map, but with an entropic regularizer\.SIAM J\. Comput\.54\(5\),pp\. S22–265\.External Links:[Document](https://dx.doi.org/10.1137/22M1539149)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[BCL\+21\]S\. Bubeck, M\. B\. Cohen, J\. R\. Lee, and Y\. T\. Lee\(2021\)Metrical task systems on trees via mirror descent and unfair gluing\.SIAM J\. Comput\.50\(3\),pp\. 909–923\.External Links:[Document](https://dx.doi.org/10.1137/19M1237879)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[BCL\+18\]S\. Bubeck, M\. B\. Cohen, Y\. T\. Lee, J\. R\. Lee, and A\. Madry\(2018\)K\-server via multiscale entropic regularization\.InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC,pp\. 3–16\.External Links:[Document](https://dx.doi.org/10.1145/3188745.3188798)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px4.p1.1)\.
- \[BN09\]N\. Buchbinder and J\. Naor\(2009\)The design of competitive online algorithms via a primal\-dual approach\.Found\. Trends Theor\. Comput\. Sci\.3\(2\-3\),pp\. 93–263\.External Links:[Document](https://dx.doi.org/10.1561/0400000024)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p1.1)\.
- \[BUR96\]W\. R\. Burley\(1996\)Traversing layered graphs using the work function algorithm\.J\. Algorithms20\(3\),pp\. 479–511\.External Links:[Document](https://dx.doi.org/10.1006/JAGM.1996.0024)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px2.p1.1)\.
- \[CKP\+91\]M\. Chrobak, H\. J\. Karloff, T\. H\. Payne, and S\. Vishwanathan\(1991\)New results on server problems\.SIAM J\. Discret\. Math\.4\(2\),pp\. 172–181\.External Links:[Document](https://dx.doi.org/10.1137/0404017)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p4.1)\.
- \[CL91\]M\. Chrobak and L\. L\. Larmore\(1991\)An optimal on\-line algorithm for k\-servers on trees\.SIAM J\. Comput\.20\(1\),pp\. 144–148\.External Links:[Document](https://dx.doi.org/10.1137/0220008)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p4.1)\.
- \[CL92\]M\. Chrobak and L\. L\. Larmore\(1992\)The server problem and on\-line games\.InOn\-Line Algorithms, Proceedings of a DIMACS Workshop,DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol\.7\.External Links:[Document](https://dx.doi.org/10.1090/DIMACS/007/02)Cited by:[§1\.1](https://arxiv.org/html/2609.15979#S1.SS1.p6.1),[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1),[Lemma 1\.1](https://arxiv.org/html/2609.15979#S1.Thmtheorem1),[§1](https://arxiv.org/html/2609.15979#S1.p3.1),[§1](https://arxiv.org/html/2609.15979#S1.p4.1)\.
- \[CKL21\]C\. Coester, E\. Koutsoupias, and P\. Lazos\(2021\)The infinite server problem\.ACM Trans\. Algorithms17\(3\),pp\. 20:1–20:23\.External Links:[Document](https://dx.doi.org/10.1145/3456632)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2609.15979#S1.p1.1)\.
- \[CK19\]C\. Coester and E\. Koutsoupias\(2019\)The onlinekk\-taxi problem\.\.InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC,pp\. 1136–1147\.External Links:[Document](https://dx.doi.org/10.1145/3313276.3316370)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1),[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px2.p1.1)\.
- \[CK21\]C\. Coester and E\. Koutsoupias\(2021\)Towards the k\-server conjecture: A unifying potential, pushing the frontier to the circle\.In48th International Colloquium on Automata, Languages, and Programming, ICALP,Vol\.198,pp\. 57:1–57:20\.External Links:[Document](https://dx.doi.org/10.4230/LIPICS.ICALP.2021.57)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p1.1),[§1](https://arxiv.org/html/2609.15979#S1.p4.1)\.
- \[CL22\]C\. Coester and J\. R\. Lee\(2022\)Pure entropic regularization for metrical task systems\.Theory Comput\.18,pp\. 1–24\.External Links:[Document](https://dx.doi.org/10.4086/TOC.2022.V018A023)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[CP26\]C\. Coester and T\. Poon\(2026\)Online 3\-taxi on general metrics\.InProceedings of the 2026 Annual ACM\-SIAM Symposium on Discrete Algorithms, SODA,pp\. 6659–6673\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611978971.238)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[CT26\]C\. Coester and A\. Tudose\(2026\)Chasing small sets optimally against adaptive adversaries\.In53rd International Colloquium on Automata, Languages, and Programming, ICALP,Vol\.374,pp\. 67:1–67:22\.External Links:[Document](https://dx.doi.org/10.4230/LIPICS.ICALP.2026.67)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[CU25\]C\. Coester and J\. Umenberger\(2025\)Smoothed analysis of online metric problems\.In33rd Annual European Symposium on Algorithms, ESA,LIPIcs, Vol\.351,pp\. 115:1–115:14\.External Links:[Document](https://dx.doi.org/10.4230/LIPICS.ESA.2025.115)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p1.1)\.
- \[DEH\+17\]S\. Dehghani, S\. Ehsani, M\. Hajiaghayi, V\. Liaghat, and S\. Seddighin\(2017\)Stochastic k\-server: how should uber work?\.In44th International Colloquium on Automata, Languages, and Programming, ICALP,LIPIcs, Vol\.80,pp\. 126:1–126:14\.External Links:[Document](https://dx.doi.org/10.4230/LIPICS.ICALP.2017.126)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p1.1)\.
- \[DW90\]A\. W\. M\. Dress and W\. Wenzel\(1990\)Valuated matroids: a new look at the greedy algorithm\.Applied Mathematics Letters3\(2\),pp\. 33–35\.External Links:[Document](https://dx.doi.org/10.1016/0893-9659%2890%2990008-G)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px3.p1.1)\.
- \[DW92\]A\. W\. M\. Dress and W\. Wenzel\(1992\)Valuated matroids\.Advances in Mathematics93\(2\),pp\. 214–250\.External Links:[Document](https://dx.doi.org/10.1016/0001-8708%2892%2990028-J)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px3.p2.1)\.
- \[FFK\+98\]A\. Fiat, D\. P\. Foster, H\. J\. Karloff, Y\. Rabani, Y\. Ravid, and S\. Vishwanathan\(1998\)Competitive algorithms for layered graph traversal\.SIAM J\. Comput\.28\(2\),pp\. 447–462\.External Links:[Document](https://dx.doi.org/10.1137/S0097539795279943)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[FKL\+91\]A\. Fiat, R\. M\. Karp, M\. Luby, L\. A\. McGeoch, D\. D\. Sleator, and N\. E\. Young\(1991\)Competitive paging algorithms\.J\. Algorithms12\(4\),pp\. 685–699\.External Links:[Document](https://dx.doi.org/10.1016/0196-6774%2891%2990041-V)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px4.p1.1)\.
- \[FRR90\]A\. Fiat, Y\. Rabani, and Y\. Ravid\(1990\)Competitive k\-server algorithms \(extended abstract\)\.In31st Annual Symposium on Foundations of Computer Science, FOCS,pp\. 454–463\.External Links:[Document](https://dx.doi.org/10.1109/FSCS.1990.89566)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p2.1)\.
- \[FR94\]A\. Fiat and M\. Ricklin\(1994\)Competitive algorithms for the weighted server problem\.Theor\. Comput\. Sci\.130\(1\),pp\. 85–99\.External Links:[Document](https://dx.doi.org/10.1016/0304-3975%2894%2990154-6)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[FKS\+25\]F\. Frei, D\. Komm, M\. Stocker, and P\. Whittington\(2025\)Time\-optimal k\-server\.In36th International Symposium on Algorithms and Computation, ISAAC,LIPIcs, Vol\.359,pp\. 32:1–32:17\.External Links:[Document](https://dx.doi.org/10.4230/LIPICS.ISAAC.2025.32)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p1.1)\.
- \[GKN25\]M\. Gehnen, R\. Klasing, and É\. Naquin\(2025\)Graph exploration with edge weight estimates\.arXiv preprint\.External Links:[Document](https://dx.doi.org/10.48550/ARXIV.2501.18496)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p1.1)\.
- \[GRO91\]E\. F\. Grove\(1991\)The harmonic online k\-server algorithm is competitive\.InProceedings of the 23rd Annual ACM Symposium on Theory of Computing STOC,pp\. 260–266\.External Links:[Document](https://dx.doi.org/10.1145/103418.103448)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p2.1)\.
- \[GKP24\]A\. Gupta, A\. Kumar, and D\. Panigrahi\(2024\)Poly\-logarithmic competitiveness for the*k*\-taxi problem\.InProceedings of the 2024 ACM\-SIAM Symposium on Discrete Algorithms, SODA,pp\. 4220–4246\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611977912.146)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[HZ24\]Z\. Huang and H\. Zhang\(2024\)Deterministic 3\-server on a circle and the limitation of canonical potentials\.Theor\. Comput\. Sci\.1020\.External Links:[Document](https://dx.doi.org/10.1016/J.TCS.2024.114844)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p4.1)\.
- \[KC82\]Jr\. Kelso and V\. P\. Crawford\(1982\)Job matching, coalition formation, and gross substitutes\.Econometrica50\(6\),pp\. 1483–1504\.External Links:[Document](https://dx.doi.org/10.2307/1913392)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px3.p1.1)\.
- \[KN03\]E\. Koutsoupias and A\. Nanavati\(2003\)The online matching problem on a line\.InApproximation and Online Algorithms, First International Workshop, WAOA,pp\. 179–191\.External Links:[Document](https://dx.doi.org/10.1007/978-3-540-24592-6%5F14)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px2.p1.1)\.
- \[KP95\]E\. Koutsoupias and C\. H\. Papadimitriou\(1995\)On the k\-server conjecture\.J\. ACM42\(5\),pp\. 971–983\.External Links:[Document](https://dx.doi.org/10.1145/210118.210128)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2609.15979#S1.p2.1)\.
- \[KP96\]E\. Koutsoupias and C\. H\. Papadimitriou\(1996\)The 2\-evader problem\.Inf\. Process\. Lett\.57\(5\),pp\. 249–252\.External Links:[Document](https://dx.doi.org/10.1016/0020-0190%2896%2900010-5)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p4.1)\.
- \[KOU99\]E\. Koutsoupias\(1999\)Weak adversaries for the k\-server problem\.In40th Annual Symposium on Foundations of Computer Science, FOCS,pp\. 444–449\.External Links:[Document](https://dx.doi.org/10.1109/SFFCS.1999.814616)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p2.1)\.
- \[KOU09\]E\. Koutsoupias\(2009\)The k\-server problem\.Comput\. Sci\. Rev\.3\(2\),pp\. 105–118\.External Links:[Document](https://dx.doi.org/10.1016/J.COSREV.2009.04.002)Cited by:[§1\.1](https://arxiv.org/html/2609.15979#S1.SS1.p4.1),[§1](https://arxiv.org/html/2609.15979#S1.p4.1)\.
- \[LEE18\]J\. R\. Lee\(2018\)Fusible hsts and the randomized k\-server conjecture\.In59th IEEE Annual Symposium on Foundations of Computer Science, FOCS,M\. Thorup \(Ed\.\),pp\. 438–449\.External Links:[Document](https://dx.doi.org/10.1109/FOCS.2018.00049)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p1.1)\.
- \[MS15\]D\. Maclagan and B\. Sturmfels\(2015\)Introduction to tropical geometry\.Graduate Studies in Mathematics, Vol\.161,American Mathematical Society,Providence, RI\.External Links:[Document](https://dx.doi.org/10.1090/gsm/161)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px3.p2.1)\.
- \[MMS88\]M\. S\. Manasse, L\. A\. McGeoch, and D\. D\. Sleator\(1988\)Competitive algorithms for on\-line problems\.InProceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC,pp\. 322–333\.External Links:[Document](https://dx.doi.org/10.1145/62212.62243)Cited by:[§1](https://arxiv.org/html/2609.15979#S1.p1.1),[§1](https://arxiv.org/html/2609.15979#S1.p2.1)\.
- \[MUI60\]T\. Muir\(1960\)The theory of determinants in the historical order of development\.Dover Publications,New York\.Note:Reprint of the 1906–1923 editionCited by:[§3\.1](https://arxiv.org/html/2609.15979#S3.SS1.p4.1)\.
- \[MUR03\]K\. Murota\(2003\)Discrete convex analysis\.SIAM Monographs on Discrete Mathematics and Applications,Society for Industrial and Applied Mathematics\.External Links:[Document](https://dx.doi.org/10.1137/1.9780898718508)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px3.p1.1)\.
- \[RIC15\]A\. Richards\(2015\)University of Oxford Advanced Research Computing\.Zenodo\.External Links:[Document](https://dx.doi.org/10.5281/zenodo.22558),[Link](https://doi.org/10.5281/zenodo.22558)Cited by:[Acknowledgments](https://arxiv.org/html/2609.15979#Sx1.p2.1)\.
- \[SCH51\]L\. Schläfli\(1851\)Über die resultante eines systemes mehrerer algebraischer gleichungen\.InGesammelte mathematische Abhandlungen,Vol\.2,pp\. 1–54\.Cited by:[§3\.1](https://arxiv.org/html/2609.15979#S3.SS1.p4.1)\.
- \[SEL20\]M\. Sellke\(2020\)Chasing convex bodies optimally\.InProceedings of the 2020 ACM\-SIAM Symposium on Discrete Algorithms, SODA,pp\. 1509–1518\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611975994.92)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px2.p1.1)\.
- \[SS06\]R\. A\. Sitters and L\. Stougie\(2006\)The generalized two\-server problem\.J\. ACM53\(3\),pp\. 437–458\.External Links:[Document](https://dx.doi.org/10.1145/1147954.1147960)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[SIT14\]R\. Sitters\(2014\)The generalized work function algorithm is competitive for the generalized 2\-server problem\.SIAM J\. Comput\.43\(1\),pp\. 96–125\.External Links:[Document](https://dx.doi.org/10.1137/120885309)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px2.p1.1)\.
- \[ST85\]D\. D\. Sleator and R\. E\. Tarjan\(1985\)Amortized efficiency of list update and paging rules\.Commun\. ACM28\(2\),pp\. 202–208\.External Links:[Document](https://dx.doi.org/10.1145/2786.2793)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px1.p1.1)\.
- \[SS04\]D\. Speyer and B\. Sturmfels\(2004\)The tropical grassmannian\.Advances in Geometry4\(3\),pp\. 389–411\.External Links:[Document](https://dx.doi.org/10.1515/advg.2004.023)Cited by:[§1\.3](https://arxiv.org/html/2609.15979#S1.SS3.SSS0.Px3.p2.1)\.

## Appendix AOmitted proofs

### Proof of Lemma[1\.1](https://arxiv.org/html/2609.15979#S1.Thmtheorem1)

###### Proof\.

By the work function recurrence, we have

wt​\(Ct−1\)\\displaystyle w\_\{t\}\(C\_\{t\-1\}\)=minx∈Ct−1⁡wt−1​\(X−x\+rt\)\+d⁡\(rt,x\)\\displaystyle=\\min\_\{x\\in C\_\{t\-1\}\}w\_\{t\-1\}\(X\-x\+r\_\{t\}\)\+d\(r\_\{t\},x\)=wt​\(Ct\)\+D⁡\(Ct−1,Ct\)\\displaystyle=w\_\{t\}\(C\_\{t\}\)\+D\(C\_\{t\-1\},C\_\{t\}\)where the last equation by definition of WFA and the fact thatwt−1​\(C\)=wt​\(C\)w\_\{t\-1\}\(C\)=w\_\{t\}\(C\)for allC∋rtC\\ni r\_\{t\}\.

Subtractwt−1​\(Ct−1\)w\_\{t\-1\}\(C\_\{t\-1\}\)from the equation and sum overtt\. The work function values on the right\-hand side telescope, andw0​\(C0\)=0w\_\{0\}\(C\_\{0\}\)=0, so

wT​\(CT\)\+∑tD⁡\(Ct−1,Ct\)=∑t\(wt​\(Ct−1\)−wt−1​\(Ct−1\)\)≤∑tExtCostt\.∎w\_\{T\}\(C\_\{T\}\)\+\\sum\_\{t\}D\(C\_\{t\-1\},C\_\{t\}\)=\\sum\_\{t\}\\bigl\(w\_\{t\}\(C\_\{t\-1\}\)\-w\_\{t\-1\}\(C\_\{t\-1\}\)\\bigr\)\\leq\\sum\_\{t\}\\mathrm\{ExtCost\}\_\{t\}\.\\qed

### Proof of Lemma[3\.1](https://arxiv.org/html/2609.15979#S3.Thmtheorem1)

###### Proof\.

Both sides multiply under composition of matrices\. Gaussian elimination expresses every invertible matrix as a product of elementary changes of basis, so it suffices to check three types\.

First, scalingeie\_\{i\}by a nonzeroccscalesei2e\_\{i\}^\{2\}byc2c^\{2\}and each of thek−1k\-1productsei​eje\_\{i\}e\_\{j\},j≠ij\\neq i, bycc\. It leaves all other products unchanged\. The determinant in the quadratic space is thereforec2\+k−1=ck\+1c^\{2\+k\-1\}=c^\{k\+1\}\.

Second, swappingeie\_\{i\}andeje\_\{j\}swaps their squares and swapsei​eℓe\_\{i\}e\_\{\\ell\}withej​eℓe\_\{j\}e\_\{\\ell\}for eachℓ∉\{i,j\}\\ell\\notin\\\{i,j\\\}\. It leavesei​eje\_\{i\}e\_\{j\}fixed\. These arek−1k\-1transpositions, giving determinant\(−1\)k−1=\(−1\)k\+1\(\-1\)^\{k\-1\}=\(\-1\)^\{k\+1\}\.

Third, consider the shear that replaceseie\_\{i\}byei\+c​eje\_\{i\}\+ce\_\{j\}and fixes the other basis vectors\. Order the quadratic monomials by their exponent ofeie\_\{i\}\. Each monomial maps to itself plus monomials having smaller exponent ofeie\_\{i\}\. Thus the induced matrix is triangular with all diagonal entries equal to one, and has determinant one\. The original shear also has determinant one\. This proves the identity for all three types and hence for their products\. ∎