Theorem 4 — a schedule with makespan at most 3 exists iff the 3-dimensional matching instance has a matching
ProvedUnrelatedSched.TwoTimes.theorem_4Let , , be disjoint sets and triples with one element in each of , , . Consider the scheduling instance on unrelated machines built from them: element jobs, one per element of , and dummy jobs; machine processes the element jobs of the three elements of in one time unit each and every other job in three time units. Then
where a schedule assigns every job to one machine, the load of a machine is the sum of the processing times of its jobs, and the makespan is the largest load.
The paper states Theorem 4 as: deciding whether a schedule with makespan at most 3 exists is NP-complete. Its proof is a reduction from 3-dimensional matching, and the equivalence above is what that proof establishes; it is what is formalized. Theorem 4 is the case of the paper's last result, Theorem 7, which recalls it.
Formalization Note NP-completeness, membership in NP and the polynomial size of the reduction are not formalized. The statement holds for all and : when there are no dummy jobs and neither side holds (when ), which stands in for the paper's "trivial 'no' instance".
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoTimes_Theorem4Instance open MatousekLP.Scheduling
namespace UnrelatedSched.TwoTimes
/-- Theorem 4 (Lenstra, Shmoys, Tardos, CWI Report OS-R8714 (1987), p. 7), in the form its proof
establishes: for the scheduling instance `thm4Times T` built from a 3-DIMENSIONAL MATCHING
instance `T` (`m` machines, `3n` element jobs, `m - n` dummy jobs, all processing times in
`{1, 3}`), there is a schedule with makespan at most `3` if and only if `T` has a matching.
"NP-complete" is not formalized. -/
theorem theorem_4 {m n : ℕ} (T : Fin m → Fin n × Fin n × Fin n) :
(∃ σ : Fin (3 * n + (m - n)) → Fin m,
makespan (fun i j => (thm4Times T i j : ℝ)) σ ≤ 3) ↔
∃ F' : Finset (Fin m), IsThreeDimMatching T F' := by sorry
end UnrelatedSched.TwoTimes
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.