Corollary 2 — for ρ < 3/2, a ρ-approximate schedule of the reduced instance decides 3-dimensional matching
ProvedUnrelatedSched.ThreeHalves.corollary_2The paper states: for every , there does not exist a polynomial -approximation algorithm for the minimum makespan problem on unrelated parallel machines, unless . Its proof (an immediate consequence of Theorem 5) establishes the following, which is what is formalized.
Let be an instance of 3-dimensional matching and consider the scheduling instance of Theorem 5 built from it. Let and let be a schedule of this instance that is within the factor of every schedule of the same instance, . Then
So the schedule returned by any -approximation algorithm with , run on the reduced instance, answers 3-DIMENSIONAL MATCHING; a polynomial such algorithm would therefore decide an NP-complete problem in polynomial time.
Formalization Note "Polynomial", "NP" and "unless " are not formalized. The -approximation property is the hypothesis for all schedules of the same reduced instance. The bound is strict, as in the paper. Values are allowed, as in the paper's "for every "; for them the hypothesis can only hold in degenerate instances.
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, Corollary 2, p. 8 (the content of its
proof): let `ρ < 3/2` and let `σ` be a schedule of the instance of Theorem 5 built from the
3-dimensional matching instance `T` that is within the factor `ρ` of every schedule of that
instance. Then `σ` has makespan at most `2` if and only if `T` has a matching; so the output of
any `ρ`-approximation algorithm on this instance decides 3-DIMENSIONAL MATCHING. -/
theorem corollary_2 {m n : ℕ} (T : Fin m → Fin n × Fin n × Fin n) (ρ : ℝ) (hρ : ρ < 3 / 2)
(σ : Fin (numJobs T) → Fin m)
(hσ : ∀ τ : Fin (numJobs T) → Fin m,
makespan (fun i r => (P T i r : ℝ)) σ ≤ ρ * makespan (fun i r => (P T i r : ℝ)) τ) :
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.