uniform_kserver_opt
For a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of requests ρ, uniform_kserver_opt k a ρ is the optimal offline cost, defined as the infimum in ℕ of the offline movement costs uniform_kserver_offline_cost a sched over all valid schedules sched for ρ.
Statement
noncomputable def uniform_kserver_opt (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (a : ∀ i, M i) (ρ : List (∀ i, M i)) : ℕ
- Defined in
- arXiv:2610.37192 Section 2
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 2
- uniform_kserver_offline_costFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of…
- uniform_kserver_is_scheduleFor a natural number k, a family of spaces M indexed by Fin k, a list of requests ρ, and a list of configurations sched, sched is a valid…
- Used by 2
- uniform_kserver_det_k_one_competitiveFor generalized 1-server on any family of uniform metric spaces M indexed by Fin 1 with decidable equality and any initial configuration a…
- uniform_kserver_det_competitiveFor a natural number k, a family of types M indexed by Fin k with decidable equality, an algorithm A : List (∀ i, M i) → (∀ i, M i), an…
Read back from the Lean
Given a natural number k, a family of types M : Fin k → Type* with decidable equality on each M i, an initial configuration a : ∀ i, M i, and a list of requests ρ : List (∀ i, M i), uniform_kserver_opt k a ρ is defined as the infimum (in ℕ, via sInf) of the set of all natural numbers c for which there exists a schedule sched : List (∀ i, M i) such that uniform_kserver_is_schedule ρ sched holds and uniform_kserver_offline_cost a sched = c.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The optimal offline cost for generalized k-server on uniform metrics. -/ noncomputable def uniform_kserver_opt (k : ℕ) {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (a : ∀ i, M i) (ρ : List (∀ i, M i)) : ℕ := sInf {c : ℕ | ∃ sched, uniform_kserver_is_schedule ρ sched ∧ uniform_kserver_offline_cost a sched = c}