Theorem 7 — with times in , , a -dimensional matching exists iff a schedule has makespan
ProvedUnrelatedSched.TwoTimes.theorem_7Let and be relatively prime natural numbers with . Let be a ground set of elements and subsets of with for every . Build the scheduling instance on unrelated machines in which machine corresponds to , there are element jobs (one per ) and dummy jobs, an element job takes time units on machine if and time units otherwise, and every dummy job takes time units on every machine. Then
- every processing time of the instance lies in , and
The paper states Theorem 7 as: the minimum makespan problem on unrelated parallel machines is NP-hard in the case that all with , . Its proof assumes without loss of generality that and are relatively prime and reduces -dimensional matching to the scheduling problem by exactly this construction; the equivalence above is what the proof establishes, and it is what is formalized. Together with Theorem 6 ( is polynomially solvable) it classifies the complexity of the cases with two processing times.
Formalization Note NP-hardness is not formalized. The general case is the paper's "without loss of generality": dividing all times by divides every makespan by ; it is not part of the statement. The hypothesis is dropped: the reduction does not use it (with coprime it only excludes , , where -dimensional matching is bipartite matching and the decision problem is easy), so the statement is stronger. The q-partite structure of -dimensional matching is not imposed, which contains the q-partite case. Ground set Fin (q * n), jobs Fin (q * n + p * (m - n)), and natural-number subtraction gives no dummy jobs when , where both sides are false for .
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoTimes_Theorem7Instance open MatousekLP.Scheduling
namespace UnrelatedSched.TwoTimes
/-- Theorem 7 (Lenstra, Shmoys, Tardos, CWI Report OS-R8714 (1987), p. 8; proof pp. 8–9), in the
form its proof establishes, for relatively prime `0 < p < q` (the paper's "without loss of
generality"): the scheduling instance `twoTimes p q n S` built from a family `S` of `m` `q`-subsets
of a ground set of `qn` elements has all processing times in `{p, q}`, and it has a schedule with
makespan at most `p * q` if and only if `S` has a matching. "NP-hard" is not formalized, and the
hypothesis `2p ≠ q` of the paper, which the reduction does not use, is dropped. -/
theorem theorem_7 {p q m n : ℕ} (hp : 0 < p) (hpq : p < q) (hcop : Nat.Coprime p q)
(S : Fin m → Finset (Fin (q * n))) (hS : ∀ i, (S i).card = q) :
(∀ i j, twoTimes p q n S i j = p ∨ twoTimes p q n S i j = q) ∧
((∃ σ : Fin (q * n + p * (m - n)) → Fin m,
makespan (fun i j => (twoTimes p q n S i j : ℝ)) σ ≤ (p * q : ℝ)) ↔
∃ F' : Finset (Fin m), IsQMatching S F') := by sorry
end UnrelatedSched.TwoTimes
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.