Theorem 5, proof (p. 8) — a schedule of makespan at most 2 yields a 3-dimensional matching
ProvedUnrelatedSched.ThreeHalves.makespan_two_gives_matchingp2o-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. If some schedule of this instance has
then the matching instance has a matching.
This is the "only if" half of the reduction of Theorem 5.
Formalization Note No assumption is made: when some lies in no triple there is no schedule of makespan at most 2 (and no matching), so the implication holds in that case as well.
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 (converse):
if the scheduling instance of Theorem 5 built from `T` has a schedule with makespan at most `2`,
then `T` has a matching. -/
theorem makespan_two_gives_matching {m n : ℕ} (T : Fin m → Fin n × Fin n × Fin n)
(σ : Fin (numJobs T) → Fin m) (hσ : makespan (fun i r => (P T i r : ℝ)) σ ≤ 2) :
HasMatching T := 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.