Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3, p. 6 — a schedule of makespan at most ddd makes the residual LP feasible

Proved
UnrelatedSched.FixedMachines.residual_lp_feasible

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

linear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

Let P=(pij)P=(p_{ij})P=(pij​) be an m×nm\times nm×n matrix of positive integer processing times, d≥0d\ge 0d≥0 an integer deadline and ε>0\varepsilon>0ε>0. Let σ\sigmaσ be a schedule with makespan at most ddd. Let LLL be its partial schedule of long assignments: LLL assigns job jjj to σ(j)\sigma(j)σ(j) when pσ(j)j>εdp_{\sigma(j)j}>\varepsilon dpσ(j)j​>εd and leaves jjj unassigned otherwise, and let tit_iti​ be the total processing time of the long assignments to machine iii. Then

  1. LLL is an admissible schedule of long assignments (ti≤dt_i\le dti​≤d for every iii), and
  2. the 000–111 matrix xxx with xij=1x_{ij}=1xij​=1 exactly when job jjj is unassigned by LLL and σ(j)=i\sigma(j)=iσ(j)=i is a feasible solution of the residual linear program: (LP) of the Rounding Theorem for the unassigned jobs, with deadlines di=d−tid_i=d-t_idi​=d−ti​ and threshold t=εdt=\varepsilon dt=εd.

In the paper: "If the instance (P,d)(P,d)(P,d) has a feasible schedule, then this includes a partial schedule of long assignments … If we then set t=εdt=\varepsilon dt=εd, we see that the linear program (LP) must once again have a feasible solution." This is what makes a 'no' answer of the procedure AεA_\varepsilonAε​ correct.

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

open MatousekLP.Scheduling

/-- §3, p. 6: if `σ` is a schedule with makespan at most `d`, then its long assignments
(`L j = some (σ j)` exactly when `p_{σ(j) j} > ε d`) form an admissible schedule of long
assignments, and the 0-1 matrix of `σ` on the remaining jobs is a feasible solution of the
residual LP with `d_i = d - t_i` and `t = ε d`. -/
theorem residual_lp_feasible {m n : ℕ} (P : Matrix (Fin m) (Fin n) ℕ)
    (hP : ∀ i j, 0 < P i j) (ε : ℝ) (hε : 0 < ε) (d : ℕ) (σ : Fin n → Fin m)
    (hσ : makespan (fun i j => (P i j : ℝ)) σ ≤ (d : ℝ)) :
    let L : Fin n → Option (Fin m) :=
      fun j => if ε * (d : ℝ) < (P (σ j) j : ℝ) then some (σ j) else none
    IsAdmissible P ε d L ∧
      (fun i j => if L j = none ∧ σ j = i then (1 : ℝ) else 0) ∈ ResidualLP P ε d L := 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
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