Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2 — FFD(L)≤119L∗+4FFD(L)\le\frac{11}{9}L^*+4FFD(L)≤911​L∗+4 and BFD(L)≤119L∗+4BFD(L)\le\frac{11}{9}L^*+4BFD(L)≤911​L∗+4 for all lists LLL

Proved
BinPacking.Decreasing.ffd_bfd_le_eleven_ninths

by mikedeng1 · Sep 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsbin-packingp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let L=(a1,…,an)L=(a_1,\dots,a_n)L=(a1​,…,an​) be any list of real numbers in (0,1](0,1](0,1], and let L∗L^*L∗ be the minimum number of unit-capacity bins into which its elements can be packed. Then First-Fit Decreasing and Best-Fit Decreasing both use at most 119L∗+4\tfrac{11}{9}L^*+4911​L∗+4 bins:

FFD(L)≤119 L∗+4andBFD(L)≤119 L∗+4.FFD(L)\le\frac{11}{9}\,L^*+4\qquad\text{and}\qquad BFD(L)\le\frac{11}{9}\,L^*+4 .FFD(L)≤911​L∗+4andBFD(L)≤911​L∗+4.

Together with the matching lower bound (Theorem 3.1) this gives the asymptotic worst-case ratio lim⁡k→∞RFFD(k)=lim⁡k→∞RBFD(k)=11/9\lim_{k\to\infty}R_{FFD}(k)=\lim_{k\to\infty}R_{BFD}(k)=11/9limk→∞​RFFD​(k)=limk→∞​RBFD​(k)=11/9 of the two decreasing heuristics, the headline result of the paper.

Formalization Note FFD(L)FFD(L)FFD(L) and BFD(L)BFD(L)BFD(L) are computed on LLL arranged into nonincreasing order by the mission's sort; the statement holds for every list LLL, sorted or not. The constants 11/911/911/9 and 444 are exactly the paper's.

Preamble
import Mathlib
import Definitions.Def_BinPacking_Decreasing_Model
Formal statement
namespace BinPacking.Decreasing

/-- Theorem 3.2 (p. 308): for every list `L` of reals in `(0, 1]`,
`FFD(L) ≤ (11/9) L* + 4` and `BFD(L) ≤ (11/9) L* + 4`. -/
theorem ffd_bfd_le_eleven_ninths (L : List ℝ) (hL : IsList L) :
    (FFD L : ℝ) ≤ (11 / 9 : ℝ) * (optBins L : ℝ) + 4 ∧
      (BFD 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. 308, Theorem 3.2
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

For every finite list L=(a1,…,an)L = (a_1, \dots, a_n)L=(a1​,…,an​) of real numbers that satisfies the predicate IsList(L)\mathrm{IsList}(L)IsList(L), both of the following hold together:

FFD(L)≤119 optBins(L)+4andBFD(L)≤119 optBins(L)+4.\mathrm{FFD}(L) \le \tfrac{11}{9}\,\mathrm{optBins}(L) + 4 \qquad\text{and}\qquad \mathrm{BFD}(L) \le \tfrac{11}{9}\,\mathrm{optBins}(L) + 4 .FFD(L)≤911​optBins(L)+4andBFD(L)≤911​optBins(L)+4.

Symbols.

  • LLL is an ordered list of reals. It may contain repeated entries, and the order of its entries is part of the input.
  • IsList(L)\mathrm{IsList}(L)IsList(L) is the only hypothesis.
  • FFD(L)\mathrm{FFD}(L)FFD(L), BFD(L)\mathrm{BFD}(L)BFD(L) and optBins(L)\mathrm{optBins}(L)optBins(L) are three quantities that depend on LLL. Each is converted to a real number before the comparison, so each takes values in a number type that embeds in R\mathbb{R}R, most likely the natural numbers.
  • All arithmetic in the inequalities is ordinary real arithmetic. The constant 119\tfrac{11}{9}911​ is the exact rational 11/911/911/9, and the additive constant is exactly 444.
  • The two inequalities are joined by "and". The same list LLL must satisfy both.

What could not be unfolded. The four names IsList\mathrm{IsList}IsList, FFD\mathrm{FFD}FFD, BFD\mathrm{BFD}BFD and optBins\mathrm{optBins}optBins come from the imported module Definitions.Def_BinPacking_Decreasing_Model. That module's contents were not provided, so this read-back cannot say what they mean. In particular, nothing in the code shown establishes any of the following:

  • that IsList(L)\mathrm{IsList}(L)IsList(L) requires the entries to lie in (0,1](0,1](0,1], or requires anything at all;
  • that FFD\mathrm{FFD}FFD and BFD\mathrm{BFD}BFD are the numbers of bins used by the First-Fit-Decreasing and Best-Fit-Decreasing heuristics;
  • that optBins(L)\mathrm{optBins}(L)optBins(L) is the minimum number of unit-capacity bins that can hold LLL.

The attached comment mentions "Theorem 3.2 (p. 308)" and entries in (0,1](0,1](0,1]. A comment does not change what the statement asserts, so it is not evidence for any of these meanings. The statement is exactly as strong as those definitions make it.

Degenerate cases.

  • Empty list (n=0n = 0n=0): the claim covers it whenever IsList\mathrm{IsList}IsList holds for the empty list. It then says FFD\mathrm{FFD}FFD and BFD\mathrm{BFD}BFD of the empty list are each at most 119 optBins+4\tfrac{11}{9}\,\mathrm{optBins} + 4911​optBins+4. If optBins\mathrm{optBins}optBins of the empty list is 000, the bound becomes ≤4\le 4≤4.
  • One-element list: it is covered in the same way, with no special treatment.
  • Additive slack: because of the +4+4+4, any list whose FFD\mathrm{FFD}FFD and BFD\mathrm{BFD}BFD values are at most 444 satisfies the claim no matter what optBins\mathrm{optBins}optBins is.
  • Junk values: if optBins\mathrm{optBins}optBins gives a default value on some inputs, such as 000 for an infimum over an empty set, the bound is checked against that value exactly as returned. The same applies if FFD\mathrm{FFD}FFD or BFD\mathrm{BFD}BFD return default values, for example when an entry exceeds bin capacity.
  • Vacuous or overly broad hypothesis: if IsList\mathrm{IsList}IsList can never be satisfied, the theorem is vacuously true. If it is always satisfied, the claim covers every real list, including lists with zero, negative, or greater-than-one entries.

None of these cases can be settled without the imported definitions.

Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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