Existence of Work Function Algorithm trajectories on arbitrary pseudometric spaces
ProvedKServerConj.exists_wfa_trajectoryexistencek-serverpseudometricwork-function
For any pseudometric space, any initial configuration of distinct points, any request sequence, and any finite horizon, there exists a trajectory that starts at the initial configuration and, at every request, minimizes the work-function-plus-movement objective over all -point configurations containing that request. The minimization is global, even when the ambient space is infinite. This supplies the existence clause of the k-server theorem for WFA.
Preamble
import Definitions.Def_KServerConj_IsWFATraj open KServerConj
Formal statement
theorem KServerConj.exists_wfa_trajectory {M : Type*} [PseudoMetricSpace M]
(k : ℕ) (hk : 1 ≤ k) (C₀ : Finset M) (hC₀ : C₀.card = k) (r : ℕ → M) (T : ℕ) :
∃ C : ℕ → Finset M, IsWFATraj k C₀ r T C := by sorrySource
Coester, Koutsoupias, Zbysiński, The k-server conjecture is true, arXiv:2609.15979, Section 1.1, equation (2) and the definition of WFA; minimizer existence follows from the exact recurrence and terminal Lipschitz continuity.