Lemma 4 — truncated items lower bound: Σ_j β_m(X_j) ≥ 17m forces expected makespan ≥ c₁
ProvedStochLoadBal.Makespan.lemma_4effective-sizeexpected-maximump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-scheduling
There is an absolute constant with the following property. Let , let be independent random variables with values in , and let be any partition of (given by an assignment , ). If
then
Here is the effective size of Definition 1 (with ). Lemma 4 is the lower bound for truncated parts; applied to the machines of a subset with , it yields the constraints (4) and (8) on every subset of machines.
Formalization Note The page's conclusion "" is written as an explicit constant quantified before everything else, so it does not depend on , or the distributions. The machines are identical here (job has size on every machine).
Preamble
import Mathlib import Definitions.Def_StochLoadBal_Makespan_Model
Formal statement
namespace StochLoadBal.Makespan
open MeasureTheory ProbabilityTheory
/-- Lemma 4 (Truncated Items Lower Bound, p. 7), with the `Ω(1)` made an absolute constant `c₁`:
for independent `[0, 1]`-valued `X_1, …, X_n` and any partition `{J_i}` of the jobs among `m`
machines (here `J_i = {j | σ j = i}`), if `Σ_j β_m(X_j) ≥ 17 m` then
`E[max_i Σ_{j ∈ J_i} X_j] ≥ c₁`. -/
theorem lemma_4 :
∃ c₁ : ℝ, 0 < c₁ ∧
∀ (m n : ℕ), 1 ≤ m →
∀ (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(X : Fin n → Ω → ℝ),
(∀ j, Measurable (X j)) → iIndepFun X P →
(∀ j ω, 0 ≤ X j ω ∧ X j ω ≤ 1) →
∀ σ : Fin n → Fin m,
17 * (m : ℝ) ≤ ∑ j, effSize P m (X j) →
c₁ ≤ expMakespan P (fun _ : Fin m => X) σ := by sorry
end StochLoadBal.Makespan
Source
Gupta, Kumar, Nagarajan & Shen, Stochastic Load Balancing on Unrelated Machines, arXiv:1904.07271v1, p. 7, Lemma 4 (proof pp. 7–8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.