Lemma 3 — a schedule of (E) satisfying inequality (1) gives the factor 2
ProvedDelayedSWPT.Extended.reductiononline-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 , and the schedule of (E) induced by Delayed SWPT. Let be an optimal schedule for (2P), and suppose is a feasible schedule for (E) such that
Then the Delayed SWPT schedule of (P) satisfies
for every feasible schedule of (P).
This is the reduction on which the whole proof rests: it remains to construct, from , a schedule 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), ; for a gap job, .
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.