Theorem 1, pinned — the effective-size LP and its rounding give an O(1)-approximation to the minimum expected makespan on unrelated machines
ProvedStochLoadBal.Makespan.theorem_1There is an absolute constant such that the following holds for every instance of stochastic load balancing on unrelated machines (sizes , measurable and integrable, with the jobs independent) and every scale . Write for the instance with sizes .
- (Lower bound.) If some assignment has expected makespan at most , then the LP (5)–(9) for with is feasible.
- (Rounding exists.) For every and every feasible solution of the LP (5)–(9) for with parameter , there is an assignment with properties (13)–(14) for , and .
- (Upper bound.) Every such assignment satisfies
Together: for , where is the minimum expected makespan, part 1 makes the LP with feasible, part 2 yields an output of the rounding and part 3 bounds its expected makespan by . With (found up to a factor by binary search) this is a -approximation, which is the content of the paper's Theorem 1: "There is an -approximation algorithm for the problem of finding an assignment to minimize the expected makespan on unrelated machines."
Formalization Note The literal claim "there is an -approximation algorithm" is not formalized as an existential over assignments, which is trivially true; the statement is about the paper's own procedure (LP, class loop, assignments with the Shmoys–Tardos guarantee (13)–(14)), none of which sees the optimum. Running time and the binary search over are not modelled. The constant replaces the of Proposition 1 (see the corrected Lemma 5).
import Mathlib import Definitions.Def_StochLoadBal_Makespan_Rounding
namespace StochLoadBal.Makespan
open MeasureTheory ProbabilityTheory
/-- Theorem 1 (p. 8), pinned to the paper's procedure. There is an absolute constant `c₀ > 0`
such that for every instance and every scale `M > 0`:
(A) if some assignment has expected makespan at most `c₀ M`, the LP (5)–(9) for the scaled
sizes `X / M` with `b = 17` is feasible;
(B) for every `b ≥ 0` and every feasible solution `y` of that LP, the rounding has an output
(an assignment with (13)–(14));
(C) every such output has expected makespan at most `(4b + 10) M`. -/
theorem theorem_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 →
∀ M : ℝ, 0 < M →
((∃ σ : Fin n → Fin m, expMakespan P X σ ≤ c₀ * M) →
∃ y : Fin m → Fin n → ℝ, LPFeasible P (scale M X) 17 y) ∧
∀ b : ℝ, 0 ≤ b → ∀ y : Fin m → Fin n → ℝ, LPFeasible P (scale M X) b y →
(∃ σ : Fin n → Fin m, IsRoundingOutput P (scale M X) b y σ) ∧
∀ σ : Fin n → Fin m, IsRoundingOutput P (scale M X) b y σ →
expMakespan P X σ ≤ (4 * b + 10) * M := by sorry
end StochLoadBal.Makespan
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.