Proof of Theorem 9.2 — for distinct , PARTITION is yes iff some schedule meets for both agents
ProvedTwoAgentSched.TotalTotal.theorem_9_2_equivalenceLet be pairwise distinct nonnegative integers, , , and consider the instance of the proof of Theorem 9.2, in which agents and each have jobs of lengths . Then
where ranges over the sequences of all jobs processed without idle time from time .
This is the correctness statement of the reduction of Theorem 9.2, for PARTITION instances without repeated values.
Formalization Note The paper states the equivalence for . With repeated values it is false: for , PARTITION has no solution (, and no subset sums to ), yet and the sequence with agents (lengths ) gives and . The paper's step "only SPT schedules can be feasible", followed by (5) and (6), assumes that a feasible schedule consists of consecutive pairs, which holds only when the lengths are distinct. The statement therefore assumes strictly increasing. PARTITION is the published PartitionYes applied to the list .
import Mathlib import Definitions.Def_TwoAgentSched_TotalTotal_Construction
namespace TwoAgentSched.TotalTotal
open ProjSchedTW.Complexity
/-- Proof of Theorem 9.2 (Agnetis et al. 2004, p. 238), corrected: for pairwise distinct integers
`p_1 < p_2 < ⋯ < p_k`, the PARTITION instance `{p_1, …, p_k}` is a yes-instance iff the
constructed instance has a sequence of all jobs with `∑ C^A_i ≤ T/2` and `∑ C^B_i ≤ T/2`.
(With repeated lengths the printed equivalence fails, e.g. for `1, 1, 1, 1, 10`.) -/
theorem theorem_9_2_equivalence {k : ℕ} (p : Fin k → ℕ) (hp : StrictMono p) :
PartitionYes (List.ofFn p) ↔
(construction p).RecYes ((bigT p : ℝ) / 2) ((bigT p : ℝ) / 2) := by sorry
end TwoAgentSched.TotalTotal
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.