Display (3) — sufficient condition for a big element to be selectable
ProvedOnlineCRS.Knapsack.big_selectable_conditionknapsackonline-contention-resolutionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selectability
Let be a big element, so , and let be a realized active set. If the total size of the other big elements in is at most , then is selectable in the big-element greedy family:
This is the pointwise implication behind the probability lower bound in display (3).
Formalization Note The printed sum in display (3) includes . The next displayed equality removes ; the corrected exclusion is used here, as recorded in the moderation notes.
Preamble
import Mathlib import Definitions.Def_OnlineCRS_Knapsack_Model
Formal statement
namespace OnlineCRS.Knapsack
/-- The sufficient condition used at display (3), p. 15, with the tested element removed
from the load as required by the equality in the next display. -/
theorem big_selectable_condition {α : Type} [Fintype α] [DecidableEq α]
(s : α → ℝ) (hs : ∀ e, 0 ≤ s e ∧ s e ≤ 1)
(A : Finset α) (e : α) (he : e ∈ bigElements s)
(hload : ∑ f ∈ ((A ∩ bigElements s).erase e), s f ≤ 1 - s e) :
OnlineCRS.Matroid.Selectable (bigFamily s) A e := by sorry
end OnlineCRS.Knapsack
Source
arXiv:1508.00142v2, proof of Theorem 2.9, display (3) and following paragraph, p. 15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.