Lemma 4.2 — for
ProvedBinPacking.SmallItems.W_ge_ffd_subLet be an integer and let be a list of real numbers all lying in . Then the weight of satisfies
This is the first half of the weighting argument: the total weight of the list falls short of the number of FFD bins by at most a constant depending on . With it gives for lists in .
Formalization Note is the minimum of over all partitions of into one- and two-element sets, with the elements indexed in nonincreasing order; see the definition file.
import Mathlib import Definitions.Def_BinPacking_SmallItems_Model import Definitions.Def_BinPacking_SmallItems_Weight
namespace BinPacking.SmallItems
/-- Lemma 4.2 (p. 316): for any integer `N ≥ 4` and `L ⊆ (1/N, 1/2]`, `W(L) ≥ FFD(L) − N + 2`. -/
theorem W_ge_ffd_sub (N : ℕ) (hN : 4 ≤ N) (L : List ℝ) (hL : IsList L)
(hrange : ∀ a ∈ L, 1 / (N : ℝ) < a ∧ a ≤ 1 / 2) :
W L ≥ (FFD L : ℝ) - (N : ℝ) + 2 := by sorry
end BinPacking.SmallItems
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a natural number with . Let be a list of reals with for every element and for every element of .
The weight is defined as follows. Let be the nonincreasing rearrangement of . Then
where:
- ranges over all permutations of with ;
- ;
- is computed with . It equals when and , and otherwise.
is the number of bins used by first-fit on . Each item goes into the lowest-indexed bin whose current sum plus the item is , or into a new bin appended at the end.
The statement asserts
computed in the reals.
Degenerate cases:
- Redundant hypothesis. The range hypothesis implies admissibility.
- Empty . and , so the claim is , which holds since .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.