Theorem 2.9 — randomized greedy OCRS for a knapsack polytope
ProvedOnlineCRS.Knapsack.knapsack_ocrsknapsackonline-contention-resolutionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-greedy-ocrs
Let be a finite ground set. Every element has a size , and let be the natural unit-capacity knapsack polytope. For every , there exists a randomized greedy OCRS for whose selectability parameter is
Thus, for every and every element , the probability that is selectable, over the independent active set and random greedy-family choice, is at least .
This is the knapsack result in Theorem 1.8 and the main target of this mission.
Formalization Note A greedy family contains the empty set, and the polytope includes the box constraints. At , the guaranteed probability is zero; the denominator is at least one throughout the stated domain.
Preamble
import Mathlib import Definitions.Def_OnlineCRS_Knapsack_Model
Formal statement
namespace OnlineCRS.Knapsack
/-- Theorem 2.9, p. 14: the natural knapsack relaxation admits a randomized greedy
OCRS with selectability `(1-2b)/(2-2b)` for `b ∈ [0,1/2]`. -/
theorem knapsack_ocrs {α : Type} [Fintype α] [DecidableEq α]
(s : α → ℝ) (hs : ∀ e, 0 ≤ s e ∧ s e ≤ 1)
(b : ℝ) (hb0 : 0 ≤ b) (hb : b ≤ 1 / 2) :
∃ w : (α → ℝ) → Finset (Finset α) → ℝ,
OnlineCRS.Matroid.IsSelectableRand (knapsackFeasible s) (knapsackPolytope s)
b ((1 - 2 * b) / (2 - 2 * b)) w := by sorry
end OnlineCRS.Knapsack
Source
arXiv:1508.00142v2, Theorem 2.9, p. 14; Theorem 1.8, p. 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.