nonclairvoyant_scheduling_offline_opt
For any natural number n and job processing vector w : Fin n → ℝ, the offline optimal total completion time nonclairvoyant_scheduling_offline_opt w is the minimum over all permutations π of Fin n of the sum ∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * w (π i).
Statement
noncomputable def nonclairvoyant_scheduling_offline_opt {n : ℕ} (w : Fin n → ℝ) : ℝ
- Defined in
- arXiv:2610.29037 Section 4 (text before Lemma 4.2)
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Used by 3
- nonclairvoyant_scheduling_offline_opt_zeroFor any natural number n, the offline optimal total completion time of the all-zero job processing vector (fun (_ : Fin n) => (0 : ℝ)) is…
- nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratioLet n be a natural number and let x, a, z : Fin n → ℝ with x = a + z, where a and z have non-negative coordinates (∀ i, 0 ≤ a i and ∀ i, 0…
- nonclairvoyant_scheduling_offline_opt_superadditiveFor any natural number n and job processing vectors a, z : Fin n → ℝ, the offline optimal total completion time satisfies superadditivity:…
Read back from the Lean
Given a natural number n (implicit) and a function w : Fin n → ℝ, nonclairvoyant_scheduling_offline_opt w is defined as the minimum (infimum) over all permutations π : Equiv.Perm (Fin n) of the sum ∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * w (π i), where i : Fin n is coerced to ℝ via its underlying value in {0, …, n - 1}. The nonemptiness of the set of permutations is witnessed by the identity permutation 1.
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 offline optimal total completion time for jobs with processing times vector w in R^n. -/ noncomputable def nonclairvoyant_scheduling_offline_opt {n : ℕ} (w : Fin n → ℝ) : ℝ := Finset.univ.inf' ⟨1, Finset.mem_univ 1⟩ (fun π : Equiv.Perm (Fin n) => ∑ i : Fin n, ((n : ℝ) - (i : ℝ)) * w (π i))