nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio
Let 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 ≤ z i). Suppose an algorithm accumulates non-negative cost C_T ≥ 0 by time T and incurs total completion cost alg_cost ≤ C_T + (2 * n / (n + 1)) * nonclairvoyant_scheduling_offline_opt z by running Round-Robin after time T. If nonclairvoyant_scheduling_offline_opt a > 0, then the competitive ratio satisfies alg_cost / nonclairvoyant_scheduling_offline_opt x ≤ max (C_T / nonclairvoyant_scheduling_offline_opt a) (2 * (n : ℝ) / ((n : ℝ) + 1)).
Statement
theorem nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio
{n : ℕ} (x a z : Fin n → ℝ)
(hxz : x = a + z)
(ha : ∀ i, 0 ≤ a i)
(hz : ∀ i, 0 ≤ z i)
(C_T : ℝ) (hC_T : 0 ≤ C_T) (alg_cost : ℝ)
(h_alg : alg_cost ≤ C_T + (2 * (n : ℝ) / ((n : ℝ) + 1)) * nonclairvoyant_scheduling_offline_opt z)
(h_opt_a : 0 < nonclairvoyant_scheduling_offline_opt a) :
alg_cost / nonclairvoyant_scheduling_offline_opt x ≤
max (C_T / nonclairvoyant_scheduling_offline_opt a) (2 * (n : ℝ) / ((n : ℝ) + 1))- Formalizes
- arXiv:2610.29037 Lemma 4.2
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- nonclairvoyant_scheduling_offline_optFor any natural number n and job processing vector w : Fin n → ℝ, the offline optimal total completion time…
- 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:…
- ratio_add_le_max_of_nonnegFor real numbers A, C, D, rho with 0 < C and 0 ≤ D, (A + rho * D) / (C + D) ≤ max (A / C) rho.
Read back from the Lean
For any natural number $n$, vectors $x, a, z : \text{Fin } n \to \mathbb{R}$, and real numbers $C_T$ and $\text{alg\_cost}$, suppose that:
1. $x = a + z$ (pointwise),
2. $a(i) \ge 0$ for all $i \in \text{Fin } n$,
3. $z(i) \ge 0$ for all $i \in \text{Fin } n$,
4. $C_T \ge 0$,
5. $\text{alg\_cost} \le C_T + \left(\frac{2n}{n + 1}\right) \cdot \text{offline\_opt}(z)$, and
6. $0 < \text{offline\_opt}(a)$,
where $\text{offline\_opt}(w)$ denotes nonclairvoyant_scheduling_offline_opt applied to $w$.
Then:
$$\frac{\text{alg\_cost}}{\text{offline\_opt}(x)} \le \max\left(\frac{C_T}{\text{offline\_opt}(a)}, \, \frac{2n}{n + 1}\right).$$
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof first establishes that offline opt is non-negative on non-negative vectors. It then uses the superadditivity of offline opt to lower bound opt(x) by opt(a) + opt(z). Together with the given upper bound on the algorithm's cost, this bounds the ratio by (C_T + rho * opt(z)) / (opt(a) + opt(z)), which is at most max(C_T / opt(a), rho) by a standard mediant inequality.
opt(z) is non-negative
Each term in the sum defining opt(z) is a product of non-negative terms.
unfold nonclairvoyant_scheduling_offline_opt refine Finset.le_inf' _ _ (fun π _ => ?_) refine Finset.sum_nonneg (fun i _ => ?_) have hi : (i : ℝ) ≤ (n : ℝ) := by exact le_of_lt (Nat.cast_lt.mpr i.isLt) have h_diff : 0 ≤ (n : ℝ) - (i : ℝ) := sub_nonneg.mpr hi exact mul_nonneg h_diff (hz (π i))
The competitive ratio bound holds.
We bound alg_cost / opt(x) by (C_T + rho * opt(z)) / (opt(a) + opt(z)) and apply ratio_add_le_max_of_nonneg.
set rho := 2 * (n : ℝ) / ((n : ℝ) + 1) have hz_nonneg : 0 ≤ nonclairvoyant_scheduling_offline_opt z := nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio_opt_nonneg z hz have h_super : nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z ≤ nonclairvoyant_scheduling_offline_opt x := by have hs := nonclairvoyant_scheduling_offline_opt_superadditive a z rw [hxz] exact hs have h_rho_nonneg : 0 ≤ rho := by dsimp [rho] refine div_nonneg ?_ ?_ · positivity · positivity have hc_nonneg : 0 ≤ C_T + rho * nonclairvoyant_scheduling_offline_opt z := by refine add_nonneg hC_T (mul_nonneg h_rho_nonneg hz_nonneg) have hd_pos : 0 < nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z := add_pos_of_pos_of_nonneg h_opt_a hz_nonneg have h_div : alg_cost / nonclairvoyant_scheduling_offline_opt x ≤ (C_T + rho * nonclairvoyant_scheduling_offline_opt z) / (nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z) := div_le_div₀ hc_nonneg h_alg hd_pos h_super have h_ratio := ratio_add_le_max_of_nonneg C_T (nonclairvoyant_scheduling_offline_opt a) (nonclairvoyant_scheduling_offline_opt z) rho h_opt_a hz_nonneg exact le_trans h_div h_ratio
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio_opt_nonneg {n : ℕ} (z : Fin n → ℝ) (hz : ∀ i, 0 ≤ z i) : 0 ≤ nonclairvoyant_scheduling_offline_opt z := by unfold nonclairvoyant_scheduling_offline_opt refine Finset.le_inf' _ _ (fun π _ => ?_) refine Finset.sum_nonneg (fun i _ => ?_) have hi : (i : ℝ) ≤ (n : ℝ) := by exact le_of_lt (Nat.cast_lt.mpr i.isLt) have h_diff : 0 ≤ (n : ℝ) - (i : ℝ) := sub_nonneg.mpr hi exact mul_nonneg h_diff (hz (π i))/-- Robustness reduction to error-detection time for Round-Robin hybrid schedules. -/theorem nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio {n : ℕ} (x a z : Fin n → ℝ) (hxz : x = a + z) (ha : ∀ i, 0 ≤ a i) (hz : ∀ i, 0 ≤ z i) (C_T : ℝ) (hC_T : 0 ≤ C_T) (alg_cost : ℝ) (h_alg : alg_cost ≤ C_T + (2 * (n : ℝ) / ((n : ℝ) + 1)) * nonclairvoyant_scheduling_offline_opt z) (h_opt_a : 0 < nonclairvoyant_scheduling_offline_opt a) : alg_cost / nonclairvoyant_scheduling_offline_opt x ≤ max (C_T / nonclairvoyant_scheduling_offline_opt a) (2 * (n : ℝ) / ((n : ℝ) + 1)) := by set rho := 2 * (n : ℝ) / ((n : ℝ) + 1) have hz_nonneg : 0 ≤ nonclairvoyant_scheduling_offline_opt z := nonclairvoyant_scheduling_round_robin_hybrid_competitive_ratio_opt_nonneg z hz have h_super : nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z ≤ nonclairvoyant_scheduling_offline_opt x := by have hs := nonclairvoyant_scheduling_offline_opt_superadditive a z rw [hxz] exact hs have h_rho_nonneg : 0 ≤ rho := by dsimp [rho] refine div_nonneg ?_ ?_ · positivity · positivity have hc_nonneg : 0 ≤ C_T + rho * nonclairvoyant_scheduling_offline_opt z := by refine add_nonneg hC_T (mul_nonneg h_rho_nonneg hz_nonneg) have hd_pos : 0 < nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z := add_pos_of_pos_of_nonneg h_opt_a hz_nonneg have h_div : alg_cost / nonclairvoyant_scheduling_offline_opt x ≤ (C_T + rho * nonclairvoyant_scheduling_offline_opt z) / (nonclairvoyant_scheduling_offline_opt a + nonclairvoyant_scheduling_offline_opt z) := div_le_div₀ hc_nonneg h_alg hd_pos h_super have h_ratio := ratio_add_le_max_of_nonneg C_T (nonclairvoyant_scheduling_offline_opt a) (nonclairvoyant_scheduling_offline_opt z) rho h_opt_a hz_nonneg exact le_trans h_div h_ratio