Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.9 — randomized greedy OCRS for a knapsack polytope

Proved
OnlineCRS.Knapsack.knapsack_ocrs

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

knapsackonline-contention-resolutionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-greedy-ocrs

Let NNN be a finite ground set. Every element has a size se∈[0,1]s_e\in[0,1]se​∈[0,1], and let P={x∈[0,1]N:∑e∈Nsexe≤1}P=\{x\in[0,1]^N:\sum_{e\in N}s_ex_e\le1\}P={x∈[0,1]N:∑e∈N​se​xe​≤1} be the natural unit-capacity knapsack polytope. For every b∈[0,1/2]b\in[0,1/2]b∈[0,1/2], there exists a randomized greedy OCRS for PPP whose selectability parameter is

c=1−2b2−2b.c=\frac{1-2b}{2-2b}.c=2−2b1−2b​.

Thus, for every x∈bPx\in bPx∈bP and every element eee, the probability that eee is selectable, over the independent active set and random greedy-family choice, is at least ccc.

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 b=1/2b=1/2b=1/2, 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
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me