Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3 — a schedule of (E) satisfying inequality (1) gives the factor 2

Proved
DelayedSWPT.Extended.reduction

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

online-algorithmsp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

Let (P) be an instance, (2P) its doubled problem, (E) its extended problem with gap jobs GGG, and πE\pi_EπE​ the schedule of (E) induced by Delayed SWPT. Let μ∗\mu^*μ∗ be an optimal schedule for (2P), and suppose σE\sigma_EσE​ is a feasible schedule for (E) such that

∑j∈JwjCj(σE)+∑g∈GwgCg(σE)≤∑j∈JwjCj(μ∗)+∑g∈GwgCg(πE).(1)\sum_{j\in J} w_j C_j(\sigma_E) + \sum_{g\in G} w_g C_g(\sigma_E) \le \sum_{j\in J} w_j C_j(\mu^*) + \sum_{g\in G} w_g C_g(\pi_E). \tag{1}j∈J∑​wj​Cj​(σE​)+g∈G∑​wg​Cg​(σE​)≤j∈J∑​wj​Cj​(μ∗)+g∈G∑​wg​Cg​(πE​).(1)

Then the Delayed SWPT schedule π\piπ of (P) satisfies

∑j∈JwjCj(π)≤2∑j∈JwjCj(S)\sum_{j\in J} w_j C_j(\pi) \le 2 \sum_{j\in J} w_j C_j(S)j∈J∑​wj​Cj​(π)≤2j∈J∑​wj​Cj​(S)

for every feasible schedule SSS of (P).

This is the reduction on which the whole proof rests: it remains to construct, from μ∗\mu^*μ∗, a schedule σE\sigma_EσE​ satisfying (1).

Formalization Note The paper's conclusion "Delayed SWPT has a competitive ratio of 2" is stated here for the one instance on which the hypothesis is made; quantifying over all instances gives the upper half of Theorem 8. In (2P), Cj(μ∗)=μj∗+2pjC_j(\mu^*) = \mu^*_j + 2p_jCj​(μ∗)=μj∗​+2pj​; for a gap job, Cg(πE)=t+1C_g(\pi_E) = t + 1Cg​(πE​)=t+1.

Preamble
import Mathlib
import Definitions.Def_DelayedSWPT_Extended_Problem
Formal statement
namespace DelayedSWPT.Extended

open DelayedSWPT.Model

/-- Lemma 3 of Anderson and Potts (2004), p. 690, for one instance: given an optimal schedule
`μ*` of (2P) and a feasible schedule `σ_E` of (E) satisfying inequality (1)
`∑_{j∈J} wⱼ Cⱼ(σ_E) + ∑_{g∈G} w_g C_g(σ_E) ≤ ∑_{j∈J} wⱼ Cⱼ(μ*) + ∑_{g∈G} w_g C_g(π_E)`,
the Delayed SWPT schedule costs at most twice any feasible schedule of (P). -/
theorem reduction {n : ℕ} (I : Instance n) (μstar : Fin n → ℕ)
    (hμ : IsOptimal (double I).r (double I).p (double I).w μstar)
    (σE : EJob I → ℕ) (hσ : IsFeasible (rE I) (pE I) σE)
    (h1 : ∑ j : Fin n, I.w j * ((σE (Sum.inl j) + I.p j : ℕ) : ℝ) +
          ∑ g : gapTimes I, gapWeight I g * ((σE (Sum.inr g) + 1 : ℕ) : ℝ) ≤
        ∑ j : Fin n, I.w j * ((μstar j + 2 * I.p j : ℕ) : ℝ) +
          ∑ g : gapTimes I, gapWeight I g * ((g.1 + 1 : ℕ) : ℝ))
    (S : Fin n → ℕ) (hS : IsFeasible I.r I.p S) :
    cost I.w I.p (dswpt I) ≤ 2 * cost I.w I.p S := by sorry

end DelayedSWPT.Extended
Source
Anderson and Potts, Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time, Math. Oper. Res. 29(3) (2004), p. 690, Lemma 3 and inequality (1)
Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

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