Proof of Theorem 5.2 — KNAPSACK is a yes-instance iff the constructed instance meets ,
ProvedTwoAgentSched.Knapsack.theorem_5_2_equivalenceknapsackp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reductionschedulingtwo-agent
Let be a KNAPSACK instance with items and . With , , consider the two-agent instance with -jobs , , one -job with , and thresholds , . Then
where ranges over the sequences of all jobs processed without idle time from time .
This combines the two directions of the proof of Theorem 5.2 into the correctness statement of the reduction.
Formalization Note The hypothesis is needed for the direction from schedules to KNAPSACK (see the counterexample in the statement of Eq. (2)). The thresholds are integers that may be negative; they are compared as real numbers with the completion times.
Preamble
import Mathlib import Definitions.Def_TwoAgentSched_Knapsack_Problem51 import Definitions.Def_TwoAgentSched_Knapsack_Construction
Formal statement
namespace TwoAgentSched.Knapsack
/-- Proof of Theorem 5.2 (Agnetis et al. 2004, p. 233), both directions together: if
`∑_i w_i u_i > 0`, the KNAPSACK instance `(u, w, b, W)` is a yes-instance iff the constructed
instance of `1‖∑ w_iC^A_i ≤ Q_A, C^B_max ≤ Q_B` with `Q_A = ŵû + (ŵ - W)p^B_1` and
`Q_B = b + p^B_1` is a yes-instance. -/
theorem theorem_5_2_equivalence {n : ℕ} (u w : Fin n → ℕ) (b W : ℤ)
(hpos : 0 < ∑ i, w i * u i) :
KnapsackYes u w b W ↔
(construction u w).RecYes ((QA u w W : ℤ) : ℝ) ((QB u w b : ℤ) : ℝ) := by sorry
end TwoAgentSched.Knapsack
Source
Agnetis, Mirchandani, Pacciarelli & Pacifici, Scheduling Problems with Two Competing Agents, Oper. Res. 52(2) (2004), p. 233, proof of Theorem 5.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.