nonclairvoyant_scheduling_upper_bound
The function nonclairvoyant_scheduling_upper_bound n lam takes a natural number n and a real number lambda (lam) and returns a real number: if 1 <= n, it returns the maximum value max_{1 <= i <= n} nonclairvoyant_scheduling_term_U n t i over the integer interval {1, ..., n} with t = (n+1)/(n-1) * lam; otherwise (if n = 0), it returns 0.
Statement
noncomputable def nonclairvoyant_scheduling_upper_bound (n : ℕ) (lam : ℝ) : ℝ
- Defined in
- arXiv:2610.29037 Theorem 4.4
- Verified
- 25 Oct 2026
- Axioms
- none listed
- Built on 1
- nonclairvoyant_scheduling_term_UThe sequence U_i(t) = (2*t*n^2 + (1-t)*i*(2*n+1-i)) / (t*n*(n+1) + (1-t)*i*(i+1)) for n jobs, index i, and parameter t.
Read back from the Lean
A definition of a function nonclairvoyant_scheduling_upper_bound taking a natural number n and a real number lam (λ), returning a real number. Letting t = ((n + 1) / (n - 1)) * lam:
- If 1 ≤ n, it returns the maximum (Finset.sup') over all natural numbers i ∈ {1, ..., n} of nonclairvoyant_scheduling_term_U n t i.
- Otherwise (if n = 0), it returns 0.
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 upper bound Psi_n(lambda) achieved by Algorithm mTSS for non-clairvoyant scheduling. -/ noncomputable def nonclairvoyant_scheduling_upper_bound (n : ℕ) (lam : ℝ) : ℝ := let t := ((n : ℝ) + 1) / ((n : ℝ) - 1) * lam if h : 1 ≤ n then (Finset.Icc 1 n).sup' (by simpa using h) (fun i => nonclairvoyant_scheduling_term_U n t i) else 0