Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5 — makespan at most 2 on the reduced instance iff a 3-dimensional matching exists

Proved
UnrelatedSched.ThreeHalves.theorem_5

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

np-hardnessp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reductionschedulingthree-dimensional-matching

The paper states: for the minimum makespan problem on unrelated parallel machines, the question of deciding if there exists a schedule with makespan at most 2 is NP-complete. Its proof establishes the following reduction, which is what is formalized.

Let T1,…,TmT_1,\dots,T_mT1​,…,Tm​ be an instance of 3-dimensional matching over AAA, BBB, CCC of size nnn, and consider the scheduling instance of Theorem 5 built from it: mmm machines (one per triple), element jobs for the elements of BBB and CCC, tj−1t_j - 1tj​−1 dummy jobs of type jjj, and processing times 111, 222, 333 as defined there. Then

∃ σ: Cmax⁡(σ)≤2⟺the instance has a 3-dimensional matching.\exists\,\sigma:\ 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.

Since 3-DIMENSIONAL MATCHING is NP-complete and the construction is polynomial, deciding whether a schedule of makespan at most 2 exists is NP-hard.

Formalization Note Membership in NP, polynomiality of the construction and NP-completeness are not formalized; only the equivalence for every instance is.

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, Theorem 5, p. 7 (the reduction its
proof establishes): the scheduling instance built from the 3-dimensional matching instance `T`
has a schedule with makespan at most `2` if and only if `T` has a matching. -/
theorem theorem_5 {m n : ℕ} (T : Fin m → Fin n × Fin n × Fin n) :
    (∃ σ : Fin (numJobs T) → Fin m, 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. 7, Theorem 5 (proof pp. 7–8)
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