Proof of Theorem 5.2, Eq. (2) — the A-jobs before the B-job of a feasible schedule solve KNAPSACK
ProvedTwoAgentSched.Knapsack.eq_2knapsackp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reductionschedulingtwo-agent
Let be a KNAPSACK instance with items such that
and consider the two-agent instance of the proof of Theorem 5.2 (, , one -job with , , ). If a sequence of all jobs satisfies and , then the set of indices of the -jobs sequenced before the -job satisfies
This is the "schedule yes KNAPSACK yes" direction of the reduction.
Formalization Note The hypothesis is added: the strict inequalities of (2) need it. Without it the statement is false: for , , , , one gets , , every sequence meets both thresholds, yet no subset has . Instances with are handled separately by the reduction of Theorem 5.2.
Preamble
import Mathlib import Definitions.Def_TwoAgentSched_Knapsack_Construction
Formal statement
namespace TwoAgentSched.Knapsack
/-- Proof of Theorem 5.2, Eq. (2) (Agnetis et al. 2004, p. 233): if `∑_i w_i u_i > 0` and a
sequence `l` of the constructed instance meets both thresholds `Q_A` and `Q_B`, then the set `S`
of A-jobs sequenced before the B-job solves KNAPSACK: `∑_{i∈S} u_i ≤ b` and `∑_{i∈S} w_i ≥ W`. -/
theorem eq_2 {n : ℕ} (u w : Fin n → ℕ) (b W : ℤ) (hpos : 0 < ∑ i, w i * u i)
(l : List (Fin (construction u w).nA ⊕ Fin (construction u w).nB))
(hl : (construction u w).Meets ((QA u w W : ℤ) : ℝ) ((QB u w b : ℤ) : ℝ) l) :
((∑ i ∈ Finset.univ.filter (fun i : Fin n => l.idxOf (aJob u w i) < l.idxOf (bJob u w)),
u i : ℕ) : ℤ) ≤ b ∧
W ≤ ((∑ i ∈ Finset.univ.filter (fun i : Fin n => l.idxOf (aJob u w i) < l.idxOf (bJob u w)),
w i : ℕ) : ℤ) := 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, Eq. (2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.