Theorem 8 — Delayed SWPT has a competitive ratio of 2

Open

DelayedSWPT.Main.competitive_ratio_two

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

competitive-analysisonline-algorithmsp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1scheduling

Consider the single-machine problem of minimizing total weighted completion time $\sum_j w_j C_j$ with release dates and no preemption, with integer release dates $r_j \ge 0$ , integer processing times $p_j \ge 1$ and positive weights $w_j$ . Let $\pi$ be the schedule produced by the online algorithm Delayed SWPT. Then $2$ is the least $\rho$ such that

\sum_{j} w_j C_j(\pi) \le \rho \sum_j w_j C_j(S)

for every instance and every feasible (offline) schedule $S$ of that instance. In words: Delayed SWPT is $2$ -competitive, and no smaller constant is valid for this algorithm.

Since no online algorithm for this problem has a competitive ratio below 2 (Hoogeveen and Vestjens, 1996), Delayed SWPT is a best possible online algorithm; that general lower bound is not part of this statement.

Formalization Note The competitive ratio is defined (p. 686) as the least such $\rho$ , so the statement is IsLeast of the set of valid $\rho$ . Comparing with every feasible schedule is the same as comparing with the offline optimum and needs no existence of an optimum. The lower half concerns Delayed SWPT only (a one-job instance with $r = 0$ , $p = 1$ suffices).

Preamble

import Mathlib
import Definitions.Def_DelayedSWPT_Model_dswpt

Formal statement

namespace DelayedSWPT.Main

open DelayedSWPT.Model

/-- Theorem 8 of Anderson and Potts (2004), p. 696: Delayed SWPT has a competitive ratio of 2.
The competitive ratio (p. 686) is the least `ρ` such that on every instance the Delayed SWPT
schedule costs at most `ρ` times every feasible (offline) schedule. -/
theorem competitive_ratio_two :
    IsLeast {ρ : ℝ | ∀ (n : ℕ) (I : Instance n) (S : Fin n → ℕ), IsFeasible I.r I.p S →
      cost I.w I.p (dswpt I) ≤ ρ * cost I.w I.p S} 2 := by sorry

end DelayedSWPT.Main

Source

Anderson and Potts, Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time, Math. Oper. Res. 29(3) (2004), p. 696, Theorem 8; competitive ratio defined on p. 686

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