Initial value of the Coester--Koutsoupias potential at a coalesced start

The Coester–Koutsoupias potential at the empty request sequence, for a coalesced initial configuration, equals $\Delta k(k+1)$.

Let $M$ be a finite metric space, let $\Delta > 0$ bound all distances of $M$, let $N = M \sqcup \bar M$ be the antipodal extension of $M$ at scale $\Delta$, and start all $k$ servers at a single point $p \in M$. Write $\Phi(\varepsilon)$ for the Coester–Koutsoupias potential (KServer.ckPotK) of the instance $(p^k, \varepsilon)$ with the empty request sequence.

Statement.

With no requests, the work function is the matching cost from the initial configuration, so the anchored potential at anchors $x_1,\dots,x_k$ is a sum of distances from $p$; the contributions of each anchor to the $k+1$ terms cancel, leaving the anchor-independent value $2\Delta\bigl(1 + 2 + \dots + k\bigr) = \Delta k (k+1)$. The identity fixes the initial value of the potential, which is what allows the telescoped step inequality to be compared with $(k+1)\,\mathrm{OPT}$ without an additive constant.

Formalization Note The coalesced initial configuration is fun _ => p, and the empty request sequence is the empty list; the value is stated as an exact equality, the minimum over anchors being attained at every anchor tuple.