Proposition 1, second sentence, corrected — if the LP (5)–(9) with b = 17 is infeasible, every expected makespan exceeds c₀ (polynomial-time solvability not formalized)
ProvedStochLoadBal.Makespan.proposition_1linear-programminglower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-scheduling
There is an absolute constant with the following property. For every instance of stochastic load balancing on unrelated machines (sizes measurable and integrable, jobs independent), if the linear program (5)–(9) with has no feasible solution, then every assignment has
Infeasibility of the LP is the lower-bound certificate of the algorithm: at scale (sizes divided by ) it certifies that the optimal expected makespan exceeds .
Formalization Note Corrected: the page has in place of , which inherits the error of Lemma 5 (3). The first sentence of the proposition (the LP is solvable in polynomial time) is not formalized; the mission has no model of running time.
Preamble
import Mathlib import Definitions.Def_StochLoadBal_Makespan_Rounding
Formal statement
namespace StochLoadBal.Makespan
open MeasureTheory ProbabilityTheory
/-- Proposition 1 (Lower Bound via LP, p. 10), second sentence, corrected: there is an absolute
constant `c₀ > 0` such that, if the LP (5)–(9) with `b = 17` is infeasible, then every
assignment has expected makespan more than `c₀` (the page has `1` in place of `c₀`). -/
theorem proposition_1 :
∃ 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 →
(¬ ∃ y : Fin m → Fin n → ℝ, LPFeasible P X 17 y) →
∀ σ : Fin n → Fin m, c₀ < expMakespan P X σ := by sorry
end StochLoadBal.Makespan
Source
Gupta, Kumar, Nagarajan & Shen, Stochastic Load Balancing on Unrelated Machines, arXiv:1904.07271v1, p. 10, Proposition 1 (second sentence)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.