Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 8.3.3 — rounding a basic optimal solution of LPR(T) gives makespan at most t* + T

Proved
MatousekLP.Scheduling.rounding_makespan_le

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

approximation-algorithmslinear-programminglp-roundingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1scheduling

Let dij>0d_{ij} > 0dij​>0 be running times of nnn jobs on mmm machines and let T≥0T \ge 0T≥0. Suppose (t∗,x∗)(t^*, x^*)(t∗,x∗) is an optimal solution of the linear program LPR(T)\mathrm{LPR}(T)LPR(T) (so LPR(T)\mathrm{LPR}(T)LPR(T) is feasible and t∗t^*t∗ is its optimal value) that satisfies Assumption 8.3.1. Then there is a schedule σ\sigmaσ, assigning every job jjj to a machine σ(j)\sigma(j)σ(j) with

xσ(j) j∗>0for every job j,x^*_{\sigma(j)\,j} > 0 \quad\text{for every job } j,xσ(j)j∗​>0for every job j,

whose makespan satisfies

max⁡i∑j: σ(j)=idij  ≤  t∗+T.\max_{i} \sum_{j:\ \sigma(j) = i} d_{ij} \;\le\; t^* + T .imax​j: σ(j)=i∑​dij​≤t∗+T.

The schedule rounds the fractional assignment x∗x^*x∗ along the edges of its support graph; this is the rounding step of the Lenstra–Shmoys–Tardos 2-approximation for scheduling on unrelated machines.

Formalization Note The book says "we can efficiently construct a schedule"; the running time of the construction is not formalized. What is formalized is the property of the schedule that the proof constructs: each job goes to a machine iii with xij∗>0x^*_{ij} > 0xij∗​>0, i.e. along an edge of the support graph. Without this constraint the statement would still be meaningful but would not describe the rounding. Machines are Fin m, jobs Fin n.

Preamble
import Mathlib
import Definitions.Def_MatousekLP_Scheduling_Schedule
import Definitions.Def_MatousekLP_Scheduling_LPRelaxation
Formal statement
namespace MatousekLP.Scheduling

/-- Lemma 8.3.3 (Matoušek–Gärtner, p. 152), in the form produced by its proof. Let
`T ≥ 0` and let `(t*, x*)` be an optimal solution of `LPR(T)` (so `LPR(T)` is feasible
and `t*` is its optimal value) satisfying Assumption 8.3.1. Then there is a schedule
`σ` that assigns every job `j` to a machine `σ(j)` with `x*_{σ(j) j} > 0` (along an
edge of the support graph `G`), and whose makespan is at most `t* + T`. -/
theorem rounding_makespan_le {m n : ℕ} (d : Matrix (Fin m) (Fin n) ℝ)
    (hd : ∀ i j, 0 < d i j) (T : ℝ) (hT : 0 ≤ T) (tstar : ℝ)
    (xstar : Matrix (Fin m) (Fin n) ℝ)
    (hopt : LPROptimal d T tstar xstar) (hA : Assumption831 d T xstar) :
    ∃ σ : Fin n → Fin m, (∀ j, 0 < xstar (σ j) j) ∧ makespan d σ ≤ tstar + T := by sorry

end MatousekLP.Scheduling
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 152, Lemma 8.3.3 (proof pp. 152–153)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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