Proof of THEOREM 1, pp. 336–337 — the instance D has a schedule of cost ≤ k iff X has an even-odd partition
ProvedGTWSched.NPC.theorem_1_reductionearliness-tardinessnp-completenessp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reductionscheduling
Let be an instance of even-odd partition (, positive integers, ) with . Build the instance D of total discrepancy with tasks :
- lengths , for , ;
- preferred midtimes for , and ;
- threshold .
Then
Formalization Note The instance D is real-valued (dLen, dMid, dK), since and can be half-integers; schedules have real, nonnegative starting times, and nonnegativity is essential here (the tasks of must fit between and ). The paper's "without loss of generality we assume that " is a hypothesis.
Preamble
import Mathlib import Definitions.Def_CookPvsNP_defs import Definitions.Def_ProjSchedTW_Complexity_Encoding import Definitions.Def_GTWSched_NPC_Schedules import Definitions.Def_GTWSched_NPC_Problems
Formal statement
namespace GTWSched.NPC
/-- Proof of THEOREM 1, pp. 336–337: for an even-odd partition instance `X` with `x₁ > 1`, the
instance D (lengths `l₀ = x₁ − 1`, `lᵢ = xᵢ`, `l₂ₙ₊₁ = 2`; midtimes `M = ∑ᵢ₌₀²ⁿ lᵢ/2` for
`T₀, …, T₂ₙ` and `2M + l₂ₙ₊₁/2` for `T₂ₙ₊₁`; threshold `k`) has a schedule of cost at most `k`
iff `X` has an even-odd partition into two parts of equal sum. -/
theorem theorem_1_reduction (x : List ℕ) (hx : EOInstance x) (hx1 : 1 < x.getD 0 0) :
EOYes x ↔ TDYesReal (dLen x) (dMid x) (dK x) := by sorry
end GTWSched.NPC
Source
Garey, Tarjan & Wilfong, One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties, Math. Oper. Res. 13 (1988), pp. 336–337, proof of THEOREM 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.