Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5, corrected (constant c₀ in place of 1) — new valid inequalities (3) and (4) with O(1) = 17

Proved
StochLoadBal.Makespan.lemma_5

by mikedeng1 · Oct 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

effective-sizep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-schedulingvalid-inequalities

There is an absolute constant c0>0c_0>0c0​>0 with the following property. Consider an instance of stochastic load balancing on m≥1m\ge1m≥1 unrelated machines: sizes Xij≥0X_{ij}\ge0Xij​≥0, measurable and integrable, with the jobs independent (the vectors (Xij)i∈[m](X_{ij})_{i\in[m]}(Xij​)i∈[m]​, j∈[n]j\in[n]j∈[n], are independent). Let σ\sigmaσ assign the jobs JiJ_iJi​ to machine iii. If

E[max⁡i∈[m]∑j∈JiXij] ≤ c0,\mathbb E\Big[\max_{i\in[m]}\sum_{j\in J_i}X_{ij}\Big]\ \le\ c_0,E[i∈[m]max​j∈Ji​∑​Xij​] ≤ c0​,

then

∑i=1m∑j∈JiE[Xij′′] ≤ 2(3)\sum_{i=1}^m\sum_{j\in J_i}\mathbb E[X''_{ij}]\ \le\ 2\qquad(3)i=1∑m​j∈Ji​∑​E[Xij′′​] ≤ 2(3)

and, for every nonempty K⊆[m]K\subseteq[m]K⊆[m] with k=∣K∣k=|K|k=∣K∣,

∑i∈K∑j∈Jiβk(Xij′) ≤ 17 k.(4)\sum_{i\in K}\sum_{j\in J_i}\beta_k(X'_{ij})\ \le\ 17\,k.\qquad(4)i∈K∑​j∈Ji​∑​βk​(Xij′​) ≤ 17k.(4)

These are the valid inequalities behind the LP (5)–(9): an assignment of small expected makespan gives a feasible integral LP solution with b=17b=17b=17.

Formalization Note This statement is corrected. The page assumes expected makespan at most 111; with that threshold (3) is false: on 100010001000 identical machines with one job per machine, each job of size 1.021.021.02 with probability 0.00350.00350.0035 and 000 otherwise, the expected makespan is about 0.9890.9890.989, but ∑jE[Xj′′]≈3.57\sum_j\mathbb E[X''_j]\approx 3.57∑j​E[Xj′′​]≈3.57. The threshold is an absolute constant c0c_0c0​ (the proof via Lemmas 1 and 4 gives any c0<min⁡(1/2,c1)c_0<\min(1/2,c_1)c0​<min(1/2,c1​)). The O(1)O(1)O(1) of (4) is the 171717 of Lemma 4. Sizes of one job on different machines may be dependent.

Preamble
import Mathlib
import Definitions.Def_StochLoadBal_Makespan_Model
Formal statement
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
Source
Gupta, Kumar, Nagarajan & Shen, Stochastic Load Balancing on Unrelated Machines, arXiv:1904.07271v1, p. 9, Lemma 5 (eqs. (3)–(4))
Human review
  • Endorsed by Shuze Chen · Oct 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 20, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me