Theorem 5, proof (p. 8) — a 3-dimensional matching yields a schedule of makespan 2
ProvedUnrelatedSched.ThreeHalves.matching_gives_makespan_twop2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reductionschedulingthree-dimensional-matching
Let be an instance of 3-dimensional matching over sets of size , and consider the scheduling instance of Theorem 5 built from it (element jobs for and , dummy jobs of type , processing times , , ). If the instance has a matching, then there is a schedule with
This is the "if" half of the reduction of Theorem 5.
Formalization Note The makespan is the published MatousekLP.Scheduling.makespan applied to the real cast of the processing-time matrix P T; schedules are maps from the enumerated jobs to the machines.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_ThreeHalves_ThreeDimMatching import Definitions.Def_UnrelatedSched_ThreeHalves_Theorem5Instance open MatousekLP.Scheduling
Formal statement
namespace UnrelatedSched.ThreeHalves
/-- Lenstra, Shmoys, Tardos, CWI Report OS-R8714 (1987), §4, proof of Theorem 5, p. 8 (first half):
if the 3-dimensional matching instance `T` has a matching, then the scheduling instance of
Theorem 5 built from `T` has a schedule with makespan at most `2`. -/
theorem matching_gives_makespan_two {m n : ℕ} (T : Fin m → Fin n × Fin n × Fin n)
(hT : HasMatching T) :
∃ σ : Fin (numJobs T) → Fin m, makespan (fun i r => (P T i r : ℝ)) σ ≤ 2 := by sorry
end UnrelatedSched.ThreeHalves
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 8, Section 4, proof of Theorem 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.