Theorem 5 — makespan at most 2 on the reduced instance iff a 3-dimensional matching exists
ProvedUnrelatedSched.ThreeHalves.theorem_5The paper states: for the minimum makespan problem on unrelated parallel machines, the question of deciding if there exists a schedule with makespan at most 2 is NP-complete. Its proof establishes the following reduction, which is what is formalized.
Let be an instance of 3-dimensional matching over , , of size , and consider the scheduling instance of Theorem 5 built from it: machines (one per triple), element jobs for the elements of and , dummy jobs of type , and processing times , , as defined there. Then
Since 3-DIMENSIONAL MATCHING is NP-complete and the construction is polynomial, deciding whether a schedule of makespan at most 2 exists is NP-hard.
Formalization Note Membership in NP, polynomiality of the construction and NP-completeness are not formalized; only the equivalence for every instance is.
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_ThreeHalves_ThreeDimMatching import Definitions.Def_UnrelatedSched_ThreeHalves_Theorem5Instance open MatousekLP.Scheduling
namespace UnrelatedSched.ThreeHalves
/-- Lenstra, Shmoys, Tardos, CWI Report OS-R8714 (1987), §4, Theorem 5, p. 7 (the reduction its
proof establishes): the scheduling instance built from the 3-dimensional matching instance `T`
has a schedule with makespan at most `2` if and only if `T` has a matching. -/
theorem theorem_5 {m n : ℕ} (T : Fin m → Fin n × Fin n × Fin n) :
(∃ σ : Fin (numJobs T) → Fin m, makespan (fun i r => (P T i r : ℝ)) σ ≤ 2) ↔
HasMatching T := by sorry
end UnrelatedSched.ThreeHalves
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.