Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 7 — with times in {p,q}\{p,q\}{p,q}, gcd⁡(p,q)=1\gcd(p,q)=1gcd(p,q)=1, a qqq-dimensional matching exists iff a schedule has makespan ≤pq\le pq≤pq

Proved
UnrelatedSched.TwoTimes.theorem_7

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

makespanmatchingnp-hardnessp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reductionscheduling

Let ppp and qqq be relatively prime natural numbers with 0<p<q0<p<q0<p<q. Let UUU be a ground set of qnqnqn elements and S1,…,SmS_1,\dots,S_mS1​,…,Sm​ subsets of UUU with ∣Si∣=q|S_i|=q∣Si​∣=q for every iii. Build the scheduling instance on mmm unrelated machines in which machine iii corresponds to SiS_iSi​, there are qnqnqn element jobs (one per u∈Uu\in Uu∈U) and p(m−n)p(m-n)p(m−n) dummy jobs, an element job uuu takes ppp time units on machine iii if u∈Siu\in S_iu∈Si​ and qqq time units otherwise, and every dummy job takes qqq time units on every machine. Then

  1. every processing time of the instance lies in {p,q}\{p,q\}{p,q}, and
∃ schedule σ with Cmax⁡(σ)≤pq  ⟺  ∃ F′⊆{1,…,m}: ∣F′∣=n, ⋃i∈F′Si=U.\exists\ \text{schedule } \sigma \text{ with } C_{\max}(\sigma)\le pq \iff \exists\, F'\subseteq\{1,\dots,m\}:\ |F'|=n,\ \bigcup_{i\in F'}S_i=U .∃ schedule σ with Cmax​(σ)≤pq⟺∃F′⊆{1,…,m}: ∣F′∣=n, i∈F′⋃​Si​=U.

The paper states Theorem 7 as: the minimum makespan problem on unrelated parallel machines is NP-hard in the case that all pij∈{p,q}p_{ij}\in\{p,q\}pij​∈{p,q} with p<qp<qp<q, 2p≠q2p\ne q2p=q. Its proof assumes without loss of generality that ppp and qqq are relatively prime and reduces qqq-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 (pij∈{1,2}p_{ij}\in\{1,2\}pij​∈{1,2} is polynomially solvable) it classifies the complexity of the cases with two processing times.

Formalization Note NP-hardness is not formalized. The general case gcd⁡(p,q)=g>1\gcd(p,q)=g>1gcd(p,q)=g>1 is the paper's "without loss of generality": dividing all times by ggg divides every makespan by ggg; it is not part of the statement. The hypothesis 2p≠q2p\ne q2p=q is dropped: the reduction does not use it (with coprime p<qp<qp<q it only excludes p=1p=1p=1, q=2q=2q=2, where qqq-dimensional matching is bipartite matching and the decision problem is easy), so the statement is stronger. The q-partite structure of qqq-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 m<nm<nm<n, where both sides are false for n≥1n\ge1n≥1.

Preamble
import Mathlib
import Definitions.Def_MatousekLP_Scheduling_Schedule
import Definitions.Def_UnrelatedSched_TwoTimes_Theorem7Instance

open MatousekLP.Scheduling
Formal statement
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
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 8, Theorem 7; proof pp. 8-9
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