Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 2 — for ρ < 3/2, a ρ-approximate schedule of the reduced instance decides 3-dimensional matching

Proved
UnrelatedSched.ThreeHalves.corollary_2

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsinapproximabilityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1schedulingthree-dimensional-matching

The paper states: for every ρ<3/2\rho < 3/2ρ<3/2, there does not exist a polynomial ρ\rhoρ-approximation algorithm for the minimum makespan problem on unrelated parallel machines, unless P=NPP = NPP=NP. Its proof (an immediate consequence of Theorem 5) establishes the following, which is what is formalized.

Let T1,…,TmT_1,\dots,T_mT1​,…,Tm​ be an instance of 3-dimensional matching and consider the scheduling instance of Theorem 5 built from it. Let ρ<3/2\rho < 3/2ρ<3/2 and let σ\sigmaσ be a schedule of this instance that is within the factor ρ\rhoρ of every schedule τ\tauτ of the same instance, Cmax⁡(σ)≤ρ Cmax⁡(τ)C_{\max}(\sigma) \le \rho\, C_{\max}(\tau)Cmax​(σ)≤ρCmax​(τ). Then

Cmax⁡(σ)≤2⟺the instance has a 3-dimensional matching.C_{\max}(\sigma) \le 2 \quad\Longleftrightarrow\quad \text{the instance has a 3-dimensional matching.}Cmax​(σ)≤2⟺the instance has a 3-dimensional matching.

So the schedule returned by any ρ\rhoρ-approximation algorithm with ρ<3/2\rho < 3/2ρ<3/2, 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 P=NPP = NPP=NP" are not formalized. The ρ\rhoρ-approximation property is the hypothesis Cmax⁡(σ)≤ρ Cmax⁡(τ)C_{\max}(\sigma) \le \rho\,C_{\max}(\tau)Cmax​(σ)≤ρCmax​(τ) for all schedules τ\tauτ of the same reduced instance. The bound ρ<3/2\rho < 3/2ρ<3/2 is strict, as in the paper. Values ρ<1\rho < 1ρ<1 are allowed, as in the paper's "for every ρ<3/2\rho < 3/2ρ<3/2"; for them the hypothesis can only hold in degenerate instances.

Preamble
import Mathlib
import Definitions.Def_MatousekLP_Scheduling_Schedule
import Definitions.Def_UnrelatedSched_ThreeHalves_ThreeDimMatching
import Definitions.Def_UnrelatedSched_ThreeHalves_Theorem5Instance

open MatousekLP.Scheduling
Formal statement
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
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 8, Corollary 2
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me