Proof of Theorem 2.9 — range of the big load and mixing probability
ProvedOnlineCRS.Knapsack.big_rangeknapsackonline-contention-resolutionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let for every element, , and for the unit-capacity knapsack polytope. If and , then
The load bound is stated on page 14; the probability bound makes explicit that the construction's parameter is a valid mixing probability.
Preamble
import Mathlib import Definitions.Def_OnlineCRS_Knapsack_Model
Formal statement
namespace OnlineCRS.Knapsack
open scoped Pointwise
/-- Proof of Theorem 2.9, p. 14: the big load lies in `[0,b]`; consequently the stated
mixing parameter is a probability on the theorem's domain. -/
theorem big_range {α : Type} [Fintype α] [DecidableEq α]
(s : α → ℝ) (hs : ∀ e, 0 ≤ s e ∧ s e ≤ 1)
(b : ℝ) (hb0 : 0 ≤ b) (hb : b ≤ 1 / 2)
(x : α → ℝ) (hx : x ∈ b • knapsackPolytope s) :
0 ≤ bigLoad s x ∧ bigLoad s x ≤ b ∧
0 ≤ bigProbability s b x ∧ bigProbability s b x ≤ 1 := by sorry
end OnlineCRS.Knapsack
Source
arXiv:1508.00142v2, proof of Theorem 2.9, p. 14, paragraph after b_big display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.