Every one-server serving schedule has optimal cost
ProvedKServerConj.one_server_cost_eq_optk-serveroffline-optimumpseudometricwork-function
Let be any pseudometric space, let be a singleton initial configuration, and let be requests. Every serving schedule with exactly one server satisfies
The service condition forces at every request time. The result therefore applies to every offline serving schedule as well as every Work Function Algorithm trajectory, on finite or infinite spaces.
Preamble
import Definitions.Def_KServerConj_confDist import Definitions.Def_KServerConj_workFn import Definitions.Def_KServerConj_IsWFATraj import Definitions.Def_KServerConj_opt import Definitions.Def_KServerConj_cl
Formal statement
theorem KServerConj.one_server_cost_eq_opt {M : Type*} [PseudoMetricSpace M]
(C₀ : Finset M) (hC₀ : C₀.card = 1) (r : ℕ → M) (T : ℕ)
(C : ℕ → Finset M) (hC : KServerConj.IsSchedule 1 C₀ r T C) :
KServerConj.wfaCost C T = KServerConj.opt 1 C₀ r T := by sorrySource
Elementary consequence of the serving-schedule definition for k=1, used for the one-server case of Coester–Koutsoupias–Zbysiński, The k-server conjecture is true, arXiv:2609.15979, Section 1.1 and Theorem 1.3 (printed p.2, PDF p.3).