§5, proof of Theorem 7 — each -dimensional matching gives a schedule with makespan
ProvedUnrelatedSched.TwoTimes.matching_gives_scheduleLet be a ground set of elements and subsets of with for every . Consider the scheduling instance of Theorem 7: machines, element jobs and dummy jobs, where an element job takes time units on a machine whose tuple contains its element and time units otherwise, and every dummy job takes time units everywhere. If the family has a matching, that is, of the tuples whose union is , then there is a schedule with
This is the easy direction of the reduction in Theorem 7.
Formalization Note The statement holds for all natural numbers , ; the standing assumptions and of Theorem 7 are not needed for this direction and are omitted, which makes the statement stronger. Schedules, loads and the makespan are those of MatousekLP.Scheduling.Schedule, with the natural-number processing times cast to reals.
import Mathlib import Definitions.Def_MatousekLP_Scheduling_Schedule import Definitions.Def_UnrelatedSched_TwoTimes_Theorem7Instance open MatousekLP.Scheduling
namespace UnrelatedSched.TwoTimes
/-- §5, proof of Theorem 7, p. 9 (Lenstra, Shmoys, Tardos, CWI Report OS-R8714 (1987)): "for each
matching there is a schedule with makespan pq". If the family `S` of `q`-subsets of the ground set
`Fin (q * n)` has a matching `F'`, the scheduling instance `twoTimes p q n S` has a schedule whose
makespan is at most `p * q`. -/
theorem matching_gives_schedule (p q : ℕ) {m n : ℕ} (S : Fin m → Finset (Fin (q * n)))
(hS : ∀ i, (S i).card = q) (F' : Finset (Fin m)) (hF' : IsQMatching S F') :
∃ σ : Fin (q * n + p * (m - n)) → Fin m,
makespan (fun i j => (twoTimes p q n S i j : ℝ)) σ ≤ (p * q : ℝ) := by sorry
end UnrelatedSched.TwoTimes
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.