Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3, p. 6 — the procedure AεA_\varepsilonAε​ is a (1+ε)(1+\varepsilon)(1+ε)-relaxed decision procedure

Proved
UnrelatedSched.FixedMachines.relaxed_procedure

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

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

Let PPP be an m×nm\times nm×n matrix of positive integer processing times, ε>0\varepsilon>0ε>0, and let VVV be any vertex selector (an LP solver that returns a vertex of each feasible residual LP, and returns nothing only for an infeasible one). Then

  1. the procedure AεA_\varepsilonAε​ run with VVV exists: there is a decision procedure DDD that tries every admissible schedule of long assignments, rounds the vertex of the residual LP, and combines the result with the long assignments; and
  2. every such procedure DDD is a (1+ε)(1+\varepsilon)(1+ε)-relaxed decision procedure: on every deadline ddd it either answers 'no', in which case no schedule has makespan at most ddd, or returns a schedule of makespan at most (1+ε)d(1+\varepsilon)d(1+ε)d.

In the paper: "We try all possible schedules of long assignments in this way, computing the remaining available time on each machine and applying the rounding procedure. Either we conclude that the instance is a 'no' instance, or we produce a schedule with makespan at most (1+ε)d(1+\varepsilon)d(1+ε)d."

Formalization Note The existence clause is where the Rounding Theorem (Theorem 1) enters: each vertex of a feasible residual LP can be rounded, within its support, to an (IP) solution. The paper applies Theorem 1 with t=εdt=\varepsilon dt=εd, which need not be an integer although Theorem 1 asks for t∈Z+t\in\mathbb Z_+t∈Z+​; the proof of Theorem 1 does not use integrality. Running time is not formalized.

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

/-- §3, p. 6: for every LP solver (vertex selector) `V`, the procedure `A_ε` run with `V` exists
(every vertex of a feasible residual LP can be rounded), and every procedure that is `A_ε` run
with `V` is a `(1 + ε)`-relaxed decision procedure: it either answers 'no', in which case no
schedule has makespan at most `d`, or produces a schedule with makespan at most `(1 + ε) d`. -/
theorem relaxed_procedure {m n : ℕ} (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) :
    (∃ D : ℕ → Option (Fin n → Fin m), IsAepsProcedure P ε V D) ∧
    ∀ D : ℕ → Option (Fin n → Fin m), IsAepsProcedure P ε V D →
      IsRelaxedDecisionProcedure P (1 + ε) D := by sorry

end UnrelatedSched.FixedMachines
Source
Lenstra, Shmoys, Tardos, Approximation algorithms for scheduling unrelated parallel machines, CWI Report OS-R8714 (1987), p. 6, Section 3, proof of Theorem 3; p. 5, definition of a ρ-relaxed decision procedure
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