gen_k_server_uniform_opt
For 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 list os of configurations satisfies List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ (os has the same length as ρ and its t-th configuration serves the t-th request) and gen_k_server_uniform_path_cost a os = c.
Statement
noncomputable def gen_k_server_uniform_opt {k m : ℕ} (a : Fin k → Fin m) (ρ : List (Fin k → Fin m)) : ℕ
- Defined in
- arXiv:2610.37192, Sec. 2: OPT(ρ), the minimum cost of an offline solution starting from a
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 1
- gen_k_server_uniform_path_costFor a start configuration x : Fin k → Fin m and a list of configurations, the path cost is defined by recursion on the list: 0 for the…
- Used by 4
- gen_k_server_uniform_one_server_competitive_oneWith one server (k = 1, configurations Fin 1 → Fin m) and any start configuration a, there are transition probabilities P with…
- gen_k_server_uniform_log_competitiveFor every k ≥ 1, every m and every start configuration a : Fin k → Fin m of generalized k-server on k uniform metrics with m points each…
- gen_k_server_uniform_opt_singletonFor k ≥ 1 and configurations a, r : Fin k → Fin m, the offline optimum of the single request r from a is 0 if a i = r i for some i, and 1…
- gen_k_server_uniform_competitiveGeneralized k-server on k uniform metrics with m points each: configurations and requests are functions Fin k → Fin m. With k m : ℕ…
Read back from the Lean
Given natural numbers k and m (implicit), a starting configuration a : Fin k → Fin m, and a sequence of request configurations ρ : List (Fin k → Fin m), gen_k_server_uniform_opt a ρ evaluates to the infimum (in ℕ) of the set of natural numbers c for which there exists a sequence of configurations os : List (Fin k → Fin m) such that:
1. os and ρ have the same length, and for every corresponding pair (o, r) in os and ρ, there exists some index i : Fin k such that o i = r i (i.e., List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ).
2. The path cost gen_k_server_uniform_path_cost a os equals 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
/-- Offline optimum OPT(ρ): the least movement cost of a sequence of configurations, started from `a`, whose t-th configuration serves the t-th request. -/ noncomputable def gen_k_server_uniform_opt {k m : ℕ} (a : Fin k → Fin m) (ρ : List (Fin k → Fin m)) : ℕ := sInf {c | ∃ os : List (Fin k → Fin m), List.Forall₂ (fun o r => ∃ i, o i = r i) os ρ ∧ gen_k_server_uniform_path_cost a os = c}