§2, proof of Theorem 1, p. 5 — at most one fractional job per machine gives loads at most d_i + t
ProvedUnrelatedSched.TwoApprox.rounding_load_boundlinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1roundingscheduling
Let , deadlines and . Let be a feasible solution of (LP), and let be a schedule supported on (that is, for every job ) such that for each machine there is at most one job with and . Then for every machine ,
This is the final step of the Rounding Theorem: the rounded schedule is a solution of (IP).
Formalization Note The paper's rounded point is the 0-1 matrix of ; "at most one job such that " is the hypothesis on above. The conclusion is the outer inequality, the load bound. The paper's is a nonnegative integer; the statement takes any real .
Preamble
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoApprox_DeadlineLP
Formal statement
namespace UnrelatedSched.TwoApprox
open MatousekLP.Scheduling
/-- §2, proof of Theorem 1, p. 5: a schedule supported on a feasible point of (LP) that, on each
machine, has at most one job with `x̃_ij < 1` has loads at most `d_i + t`. -/
theorem rounding_load_bound {m n : ℕ} (P : Matrix (Fin m) (Fin n) ℕ) (d : Fin m → ℝ) (t : ℝ)
(ht : 0 ≤ t) (x : Matrix (Fin m) (Fin n) ℝ) (hx : LPFeasible P d t x)
(σ : Fin n → Fin m) (hσ : SupportedOn x σ)
(hfrac : ∀ i (j₁ j₂ : Fin n), σ j₁ = i → σ j₂ = i → x i j₁ < 1 → x i j₂ < 1 → j₁ = j₂) :
∀ i, load (realTimes P) σ i ≤ d i + t := by sorry
end UnrelatedSched.TwoApprox
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 5, §2, proof of Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.