gen_k_server_uniform_competitive
Generalized k-server on k uniform metrics with m points each: configurations and requests are functions Fin k → Fin m. With k m : ℕ implicit, the predicate takes, in this order, P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ, a start configuration a : Fin k → Fin m and a real γ, and holds when gen_k_server_uniform_is_rand_alg P and there is a real constant c such that for every ρ : List (Fin k → Fin m), gen_k_server_uniform_expected_cost P a ρ ≤ γ * (gen_k_server_uniform_opt a ρ : ℝ) + c.
Statement
def gen_k_server_uniform_competitive {k m : ℕ} (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ) (a : Fin k → Fin m) (γ : ℝ) : Prop
- Defined in
- arXiv:2610.37192, Sec. 2: a randomized online algorithm is γ-competitive against an oblivious adversary if E[ALG(ρ)] ≤ γ·OPT(ρ) + c for every finite request sequence ρ, with c allowed to depend on the start configuration a
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 3
- gen_k_server_uniform_is_rand_algGeneralized k-server where each of the k servers moves in its own copy of the uniform metric on m points: configurations and requests are…
- gen_k_server_uniform_expected_costGeneralized k-server on k uniform metrics with m points each: configurations and requests are functions Fin k → Fin m. With k m : ℕ…
- gen_k_server_uniform_optFor a start configuration a : Fin k → Fin m and a request list ρ, OPT is the infimum (sInf in ℕ) of the natural numbers c such that some…
Read back from the Lean
Given implicit natural numbers k and m, a transition probability function P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ, an initial configuration a : Fin k → Fin m, and a competitive ratio γ : ℝ, gen_k_server_uniform_competitive P a γ asserts that:
1. P is a valid randomized online algorithm (gen_k_server_uniform_is_rand_alg P), meaning that for all request histories past : List (Fin k → Fin m), current requests r : Fin k → Fin m, and current states x : Fin k → Fin m:
- for every state y : Fin k → Fin m, 0 ≤ P past r x y,
- the sum over all y : Fin k → Fin m of P past r x y equals 1, and
- for every y : Fin k → Fin m, if P past r x y ≠ 0, then there exists some coordinate i : Fin k such that y i = r i (the request is served);
AND
2. There exists an additive constant c : ℝ such that for all request sequences ρ : List (Fin k → Fin m), the expected cost of running P on ρ starting from configuration a is at most γ * (gen_k_server_uniform_opt a ρ : ℝ) + 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
/-- `P` is a γ-competitive randomized online algorithm (oblivious adversary) for generalized k-server on uniform metrics `Fin m`, started in `a`. -/ def gen_k_server_uniform_competitive {k m : ℕ} (P : List (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → (Fin k → Fin m) → ℝ) (a : Fin k → Fin m) (γ : ℝ) : Prop := gen_k_server_uniform_is_rand_alg P ∧ ∃ c : ℝ, ∀ ρ : List (Fin k → Fin m), gen_k_server_uniform_expected_cost P a ρ ≤ γ * (gen_k_server_uniform_opt a ρ : ℝ) + c