Section 4, p. 314 — if then
ProvedBinPacking.Decreasing.ffd_le_eleven_ninths_large_itemsapproximation-algorithmsbin-packingp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a list of real numbers each lying in the half-open interval . Then First-Fit Decreasing satisfies
This is the reduced form of Theorem 3.2 to which Section 3 of the paper brings the whole result: Lemma 3.3 (with , ) shows that it suffices to consider lists in , and Theorem 3.4 (since ) transfers the bound from FFD to BFD. The paper states it as "the crucial assertion" of Theorem 3.2 and gives an outline of its proof; the complete proof is in Johnson's 1973 thesis.
Preamble
import Mathlib import Definitions.Def_BinPacking_Decreasing_Model
Formal statement
namespace BinPacking.Decreasing
/-- The reduced assertion of Section 4 (p. 314; restated p. 322): if every element of `L` lies
in `(2/11, 1]`, then `FFD(L) ≤ (11/9) L* + 4`. -/
theorem ffd_le_eleven_ninths_large_items (L : List ℝ) (hL : IsList L)
(h211 : ∀ a ∈ L, (2 / 11 : ℝ) < a) :
(FFD L : ℝ) ≤ (11 / 9 : ℝ) * (optBins L : ℝ) + 4 := by sorry
end BinPacking.Decreasing
Source
Johnson, Demers, Ullman, Garey, Graham, Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms, SIAM J. Comput. 3(4) (1974), p. 314, Section 4 (opening sentence); restated p. 322
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Notation:
- is a list of reals with every entry in . The hypotheses are and .
- is the least number of unit bins into which the entries can be assigned with every bin sum .
- is the number of bins used when the entries, sorted into nonincreasing order by a stable merge sort, are placed one at a time from no bins into the lowest-indexed bin whose current sum plus the item is , otherwise into a new bin.
The statement asserts
as a real inequality.
For empty , both and are , and the claim reads .
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.