Lemma 5, corrected (constant c₀ in place of 1) — new valid inequalities (3) and (4) with O(1) = 17
ProvedStochLoadBal.Makespan.lemma_5There is an absolute constant with the following property. Consider an instance of stochastic load balancing on unrelated machines: sizes , measurable and integrable, with the jobs independent (the vectors , , are independent). Let assign the jobs to machine . If
then
and, for every nonempty with ,
These are the valid inequalities behind the LP (5)–(9): an assignment of small expected makespan gives a feasible integral LP solution with .
Formalization Note This statement is corrected. The page assumes expected makespan at most ; with that threshold (3) is false: on identical machines with one job per machine, each job of size with probability and otherwise, the expected makespan is about , but . The threshold is an absolute constant (the proof via Lemmas 1 and 4 gives any ). The of (4) is the of Lemma 4. Sizes of one job on different machines may be dependent.
import Mathlib import Definitions.Def_StochLoadBal_Makespan_Model
namespace StochLoadBal.Makespan
open MeasureTheory ProbabilityTheory
/-- Lemma 5 (New Valid Inequalities, p. 9), corrected: the threshold `1` on the expected
makespan is replaced by an absolute constant `c₀ > 0` (with `1`, inequality (3) is false), and
the `O(1)` of (4) is `17`. If an assignment `σ` has expected makespan at most `c₀`, then
(3) `Σ_i Σ_{j ∈ J_i} E[X''_{ij}] ≤ 2` and
(4) `Σ_{i ∈ K} Σ_{j ∈ J_i} β_k(X'_{ij}) ≤ 17 k` for every nonempty `K ⊆ [m]`, `k = |K|`. -/
theorem lemma_5 :
∃ c₀ : ℝ, 0 < c₀ ∧
∀ (m n : ℕ), 1 ≤ m →
∀ (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(X : Fin m → Fin n → Ω → ℝ),
(∀ i j, Measurable (X i j)) → (∀ i j ω, 0 ≤ X i j ω) →
(∀ i j, Integrable (X i j) P) → iIndepFun (fun j ω i => X i j ω) P →
∀ σ : Fin n → Fin m, expMakespan P X σ ≤ c₀ →
(∑ j, ∫ ω, exc (X (σ j) j ω) ∂P ≤ 2) ∧
∀ K : Finset (Fin m), K.Nonempty →
∑ i ∈ K, ∑ j ∈ Finset.univ.filter (fun j => σ j = i),
effSize P K.card (fun ω => trunc (X i j ω)) ≤ 17 * (K.card : ℝ) := by sorry
end StochLoadBal.Makespan
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.