Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — binary search over rounded vertices of (LP) is a 2-approximation algorithm for R||C_max

Proved
UnrelatedSched.TwoApprox.theorem_2

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

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

Consider the minimum makespan problem on unrelated parallel machines: m≥1m\ge 1m≥1 machines, nnn jobs, and processing times pijp_{ij}pij​ that are positive integers; let OPT\mathrm{OPT}OPT be the minimum makespan. Fix any vertex selector VVV (an LP solver returning, for each deadline d∈Nd\in\mathbb Nd∈N, a vertex of (LP) with d1=⋯=dm=t=dd_1=\dots=d_m=t=dd1​=⋯=dm​=t=d when that LP is feasible, and 'none' otherwise). Then

  1. an LP rounding procedure driven by VVV exists: a decision procedure DDD that answers 'no' exactly when VVV does, and otherwise answers with a schedule supported on the chosen vertex that solves (IP) with d1=⋯=dm=t=dd_1=\dots=d_m=t=dd1​=⋯=dm​=t=d; and
  2. for every such DDD, the schedule σD\sigma_DσD​ output by the binary search of Lemma 1 driven by DDD satisfies
makespan⁡(σD)≤2⋅OPT.\operatorname{makespan}(\sigma_D)\le 2\cdot\mathrm{OPT}.makespan(σD​)≤2⋅OPT.

This is the paper's main result: a polynomial algorithm for R ∥ Cmax⁡R\,\|\,C_{\max}R∥Cmax​ with a constant performance guarantee, where the best bound known before was 2m2\sqrt m2m​ times the optimum (Davis and Jaffe).

Formalization Note The paper states: "There is a 2-approximation algorithm for the minimum makespan problem on unrelated parallel machines that runs in time bounded by a polynomial in the input size." Its proof establishes that binary search (Lemma 1) over the procedure that rounds a vertex of (LP) with d1=⋯=dm=t=dd_1=\dots=d_m=t=dd1​=⋯=dm​=t=d (Theorem 1) outputs a schedule of makespan at most 2⋅OPT2\cdot\mathrm{OPT}2⋅OPT; this guarantee, for the algorithm as defined and for every choice of vertex by the LP solver, is what is formalized. Polynomial running time (Lemma 1's iteration count, the ellipsoid method, the rounding) is not. The output is tied to the algorithm: it is the binary search's output, and every 'almost' answer is a rounding of the LP solver's vertex, so no optimal schedule can be substituted for it.

Preamble
import Mathlib
import Definitions.Def_MatousekLP_Scheduling_Schedule
import Definitions.Def_UnrelatedSched_TwoApprox_DeadlineLP
import Definitions.Def_UnrelatedSched_TwoApprox_Algorithm
Formal statement
namespace UnrelatedSched.TwoApprox

open MatousekLP.Scheduling

/-- Theorem 2, p. 6: for every vertex selector, the LP rounding procedure exists, and the binary
search of Lemma 1 driven by any such procedure outputs a schedule of makespan at most twice the
optimum. -/
theorem theorem_2 {m n : ℕ} (hm : 0 < m) (P : Matrix (Fin m) (Fin n) ℕ) (hP : ∀ i j, 0 < P i j)
    (V : ℕ → Option (Matrix (Fin m) (Fin n) ℝ)) (hV : IsVertexSelector P V)
    (σopt : Fin n → Fin m) (hopt : IsOptimalSchedule (realTimes P) σopt) :
    (∃ D : DecisionProcedure m n, IsLPRoundingProcedure P V D) ∧
      ∀ D : DecisionProcedure m n, IsLPRoundingProcedure P V D →
        makespan (realTimes P) (binarySearch P hm D) ≤ 2 * makespan (realTimes P) σopt := by sorry

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