Theorem 5, proof (p. 7) — the total number of dummy jobs is m − n
ProvedUnrelatedSched.ThreeHalves.dummy_countcountingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingthree-dimensional-matching
Let be an instance of 3-dimensional matching over sets of size , and let be the number of triples containing . Suppose every lies in at least one triple, for all . Then the number of dummy jobs of the instance of Theorem 5 is :
The paper notes this in passing ("the total number of dummy jobs is , as before"); it is the count that leaves exactly one machine per type free for element jobs.
Formalization Note The identity is stated as to avoid subtracting from in the natural numbers; under the subtraction is exact.
Preamble
import Mathlib import Definitions.Def_UnrelatedSched_ThreeHalves_Theorem5Instance
Formal statement
namespace UnrelatedSched.ThreeHalves
/-- Lenstra, Shmoys, Tardos, CWI Report OS-R8714 (1987), §4, proof of Theorem 5, p. 7: when every
`a_j` lies in at least one triple (`t_j ≥ 1`), the total number `Σ_j (t_j − 1)` of dummy jobs is
`m − n`, stated without subtraction as `Σ_j (t_j − 1) + n = m`. -/
theorem dummy_count {m n : ℕ} (T : Fin m → Fin n × Fin n × Fin n)
(hT : ∀ j : Fin n, 1 ≤ typeCount T j) :
(∑ j : Fin n, (typeCount T j - 1)) + n = m := by sorry
end UnrelatedSched.ThreeHalves
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 7, Section 4, proof of Theorem 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.