Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.10 — a job finishing by r⋅lbr\cdot\mathrm{lb}r⋅lb has a fraction at least 1−4/r1-4/r1−4/r of good long-operations

Proved
FlowJobHardness.ColoringReduction.lemma_3_10

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

flow-shopjob-shoplower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let GGG be a simple graph on nnn vertices with a proper colouring into ddd classes, let r≥1r \ge 1r≥1 be an integer, and let S(r,d)S(r,d)S(r,d) be the generalized flow shop instance of the colouring reduction, with lb=r2d\mathrm{lb}=r^{2d}lb=r2d. Fix a feasible schedule of all jobs.

Let jjj be a job of frequency fff, so jjj has r2fr^{2f}r2f long-operations, each of length r2(d−f)r^{2(d-f)}r2(d−f). If the completion time of jjj is at most r⋅lbr\cdot\mathrm{lb}r⋅lb, then the number of good long-operations of jjj (those followed by the next long-operation of jjj within delay r24r2(d−f)\tfrac{r^2}{4}r^{2(d-f)}4r2​r2(d−f)) satisfies

#{good long-operations of j} ≥ (1−4r) r2f.\#\{\text{good long-operations of } j\} \ \ge\ \Big(1-\frac{4}{r}\Big)\, r^{2f}.#{good long-operations of j} ≥ (1−r4​)r2f.

In the paper this is applied to the jobs that finish within L⋅lb≤r⋅lbL\cdot \mathrm{lb} \le r\cdot\mathrm{lb}L⋅lb≤r⋅lb. It is the analogue for S(r,d)S(r,d)S(r,d) of Lemma 2.2 for the flow shop gap instance.

Formalization Note. The paper's context ("all jobs (that were not disregarded) have completion time at most L⋅lbL\cdot\mathrm{lb}L⋅lb, which is by assumption at most r⋅lbr\cdot\mathrm{lb}r⋅lb") becomes the hypothesis Cj≤r⋅r2dC_j \le r\cdot r^{2d}Cj​≤r⋅r2d on the single job jjj. The fraction is stated as a count, multiplied out by the number r2fr^{2f}r2f of long-operations of jjj.

Preamble
import Mathlib
import Definitions.Def_JobShopLTAS_Core_Instance
import Definitions.Def_FlowJobHardness_ColoringReduction_Construction
import Definitions.Def_FlowJobHardness_ColoringReduction_Schedule

open JobShopLTAS.Core
Formal statement
namespace FlowJobHardness.ColoringReduction

/-- **Lemma 3.10** (Mastrolilli–Svensson 2011, p. 20:18). For `r ≥ 1`, in a feasible schedule
of `S(r, d)`, every job `q` of frequency `f` whose completion time is at most `r · lb =
r · r^{2d}` has at least `(1 - 4/r) · r^{2f}` good long-operations, i.e. a fraction at least
`1 - 4/r` of its `r^{2f}` long-operations is good. -/
theorem lemma_3_10 {n d : ℕ} (G : SimpleGraph (Fin n)) (c : G.Coloring (Fin d)) (r : ℕ)
    (hr : 1 ≤ r) (s : (inst G c r).Op → ℝ)
    (hs : (inst G c r).IsFeasibleSchedule Finset.univ s)
    (q : Fin (size r d n)) (hq : jobCompletion G c r s q ≤ (r : ℝ) * (R r d : ℝ)) :
    (1 - 4 / (r : ℝ)) * (r : ℝ) ^ (2 * jobFreq c q) ≤ (goodCount G c r s q : ℝ) := by sorry

end FlowJobHardness.ColoringReduction
Source
Mastrolilli, Svensson, Hardness of Approximating Flow and Job Shop Scheduling Problems, J. ACM 58(5) (2011), Article 20, p. 20:18, Lemma 3.10 (with the definition of good long-operations, p. 20:10)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

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