Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 — enumerating long assignments and rounding the LP gives a (1+ε)(1+\varepsilon)(1+ε)-approximation for makespan

Proved
UnrelatedSched.FixedMachines.theorem_3

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

approximation-algorithmslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

Let m≥1m\ge 1m≥1 machines and nnn jobs be given, with a matrix P=(pij)P=(p_{ij})P=(pij​) of positive integer processing times, and let OPT\mathrm{OPT}OPT be the minimum makespan over all schedules. Let ε>0\varepsilon>0ε>0 and let VVV be any LP solver returning a vertex of each feasible residual LP (a vertex selector). Then the procedure AεA_\varepsilonAε​ run with VVV exists, and for every such procedure the binary search of Lemma 1 driven by it returns a schedule σ\sigmaσ with

makespan(σ)≤(1+ε) OPT.\mathrm{makespan}(\sigma) \le (1+\varepsilon)\,\mathrm{OPT}.makespan(σ)≤(1+ε)OPT.

The paper states: "Let mmm be a fixed integer. There is a family {Aε}\{A_\varepsilon\}{Aε​} of algorithms such that, for each ε>0\varepsilon>0ε>0, AεA_\varepsilonAε​ is a (1+ε)(1+\varepsilon)(1+ε)-approximation algorithm for the minimum makespan problem on mmm unrelated parallel machines that requires time bounded by a polynomial in the input size and space bounded by a polynomial in mmm, log⁡(1/ε)\log(1/\varepsilon)log(1/ε), and the input size." Its proof establishes the approximation guarantee above for the algorithm it describes (enumerate long assignments, round a vertex of the residual LP, binary search on the deadline), which is what is formalized.

The result is a polynomial approximation scheme for every fixed number of machines whose space requirement is polynomial in log⁡(1/ε)\log(1/\varepsilon)log(1/ε), in contrast with the earlier scheme of Horowitz and Sahni.

Formalization Note The time and space bounds and the hypothesis that mmm is fixed are not formalized; the guarantee is stated for every m≥1m\ge 1m≥1. The optimum is given by an optimal schedule σopt\sigma_{\mathrm{opt}}σopt​. The output schedule is tied to the algorithm: it is produced by the binary search from answers of the procedure AεA_\varepsilonAε​, each of which extends an admissible schedule of long assignments and rounds a vertex of the residual LP within its support.

Preamble
import Mathlib
import Definitions.Def_MatousekLP_Scheduling_Schedule
import Definitions.Def_UnrelatedSched_FixedMachines_LongAssignment
import Definitions.Def_UnrelatedSched_FixedMachines_BinarySearch
Formal statement
namespace UnrelatedSched.FixedMachines

open MatousekLP.Scheduling

/-- Theorem 3 (p. 6), as its proof establishes it: for every number `m ≥ 1` of machines, every
positive integer processing-time matrix `P`, every `ε > 0` and every LP solver `V`, the
procedure `A_ε` run with `V` exists, and the binary search of Lemma 1 driven by any such
procedure outputs a schedule whose makespan is at most `(1 + ε)` times the optimal makespan. -/
theorem theorem_3 {m n : ℕ} (hm : 0 < m) (P : Matrix (Fin m) (Fin n) ℕ)
    (hP : ∀ i j, 0 < P i j) (ε : ℝ) (hε : 0 < ε)
    (V : ℕ → (Fin n → Option (Fin m)) → Option (Matrix (Fin m) (Fin n) ℝ))
    (hV : IsVertexSelector P ε V) (σopt : Fin n → Fin m)
    (hopt : IsOptimalSchedule (fun i j => (P i j : ℝ)) σopt) :
    (∃ D : ℕ → Option (Fin n → Fin m), IsAepsProcedure P ε V D) ∧
    ∀ D : ℕ → Option (Fin n → Fin m), IsAepsProcedure P ε V D →
      makespan (fun i j => (P i j : ℝ)) (binarySearch hm P D) ≤
        (1 + ε) * makespan (fun i j => (P i j : ℝ)) σopt := by sorry

end UnrelatedSched.FixedMachines
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 6, Theorem 3
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