Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1 — for L⊆(0,1/2]L \subseteq (0, 1/2]L⊆(0,1/2], FFD(L)≤(71/60)L∗+5FFD(L) \le (71/60)L^* + 5FFD(L)≤(71/60)L∗+5

Proved
BinPacking.SmallItems.ffd_le_seventy_one_sixtieths

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

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

Let LLL be a list of real numbers, each lying in (0,1/2](0,1/2](0,1/2], and let L∗L^*L∗ be the minimum number of unit-capacity bins into which LLL can be packed. Then First-Fit Decreasing uses

FFD(L)  ≤  7160 L∗+5FFD(L)\;\le\;\frac{71}{60}\,L^*+5FFD(L)≤6071​L∗+5

bins.

The constant 71/6071/6071/60 is best possible: the Remark after the theorem gives lists with FFD(L)=7160L∗FFD(L)=\tfrac{71}{60}L^*FFD(L)=6071​L∗ whose elements are all below 1/31/31/3. The theorem is the model case of the weighting-function method that proves the general 11/911/911/9 bound for FFD.

Formalization Note FFD(L)FFD(L)FFD(L) is First-Fit applied to the nonincreasing rearrangement of LLL, and L∗L^*L∗ is optBins L; see the model definition file.

Preamble
import Mathlib
import Definitions.Def_BinPacking_SmallItems_Model
Formal statement
namespace BinPacking.SmallItems

/-- Theorem 4.1 (p. 314): for all lists `L ⊆ (0, 1/2]`, `FFD(L) ≤ (71/60)L* + 5`. -/
theorem ffd_le_seventy_one_sixtieths (L : List ℝ) (hL : IsList L) (hhalf : ∀ a ∈ L, a ≤ 1 / 2) :
    (FFD L : ℝ) ≤ 71 / 60 * (optBins L : ℝ) + 5 := by sorry

end BinPacking.SmallItems
Source
Johnson, Demers, Ullman, Garey, Graham, Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms, SIAM J. Comput. 3(4) (1974), p. 314, Theorem 4.1
Read-back

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

For every list LLL of real numbers that satisfies the predicate IsList(L)\mathrm{IsList}(L)IsList(L) and in which every entry aaa satisfies a≤12a \le \tfrac12a≤21​, the statement asserts

FFD(L)  ≤  7160 optBins(L)+5.\mathrm{FFD}(L) \;\le\; \frac{71}{60}\,\mathrm{optBins}(L) + 5 .FFD(L)≤6071​optBins(L)+5.

Objects involved.

  • L=(a1,…,an)L = (a_1, \dots, a_n)L=(a1​,…,an​) is a finite list of real numbers. Its length n≥0n \ge 0n≥0 is arbitrary. Order and repeated values are allowed.
  • IsList(L)\mathrm{IsList}(L)IsList(L) is a hypothesis about LLL. It comes from the imported module Definitions.Def_BinPacking_SmallItems_Model, and that module's text is not part of the code given here. So this read-back cannot say what the hypothesis requires, for example whether it forces every entry to be strictly positive or bounds the entries in some other way. It is exactly the condition that module defines, nothing more or less.
  • FFD(L)\mathrm{FFD}(L)FFD(L) and optBins(L)\mathrm{optBins}(L)optBins(L) also come from that imported module, and their definitions are not shown either. From the names, one would guess that FFD(L)\mathrm{FFD}(L)FFD(L) is the number of bins the First-Fit-Decreasing heuristic uses on LLL, and that optBins(L)\mathrm{optBins}(L)optBins(L) is the least number of bins that can hold LLL. The code itself does not confirm either guess. What the statement does show is that both are converted to real numbers before being compared, so they are presumably natural-number (or integer) counts. The inequality is checked in R\mathbb{R}R.
  • The only other explicit hypothesis is the upper bound a≤12a \le \tfrac12a≤21​ for every entry aaa of LLL. The statement itself sets no lower bound on the entries. Any lower bound, such as a>0a > 0a>0, exists only if IsList\mathrm{IsList}IsList imposes it.
  • The constants are exact. The multiplicative factor is 7160\tfrac{71}{60}6071​ and the additive constant is 555. The inequality is non-strict (≤\le≤). It is claimed for every admissible LLL, not only in the limit as optBins(L)→∞\mathrm{optBins}(L) \to \inftyoptBins(L)→∞.

The comment attached to the declaration says "for all lists L⊆(0,1/2]L \subseteq (0, 1/2]L⊆(0,1/2]". That comment is documentation, not part of the formal statement. The formal hypotheses are exactly IsList(L)\mathrm{IsList}(L)IsList(L) and a≤12a \le \tfrac12a≤21​ for every a∈La \in La∈L.

Degenerate cases.

  • Empty list. If LLL is empty and IsList\mathrm{IsList}IsList accepts it, the upper-bound hypothesis holds vacuously. The statement then asserts FFD( )≤7160 optBins( )+5\mathrm{FFD}(\,) \le \tfrac{71}{60}\,\mathrm{optBins}(\,) + 5FFD()≤6071​optBins()+5, whatever values the imported definitions give for the empty list. If both are 000, this reads 0≤50 \le 50≤5.
  • One-element list. For L=(a)L = (a)L=(a) with a≤12a \le \tfrac12a≤21​, the claim is FFD((a))≤7160 optBins((a))+5\mathrm{FFD}((a)) \le \tfrac{71}{60}\,\mathrm{optBins}((a)) + 5FFD((a))≤6071​optBins((a))+5.
  • Zero or negative entries. Whether entries equal to 000 or below 000 are admitted depends only on IsList\mathrm{IsList}IsList. If they are admitted, the statement covers them too, with whatever values FFD\mathrm{FFD}FFD and optBins\mathrm{optBins}optBins assign to such lists.
  • Vacuous cases. If IsList\mathrm{IsList}IsList can never hold together with the ≤12\le \tfrac12≤21​ bound, the statement is vacuously true. The code shown does not let one decide this.
  • Small inputs. Because of the additive +5+5+5, the inequality holds automatically for any admissible LLL with FFD(L)≤5\mathrm{FFD}(L) \le 5FFD(L)≤5, provided optBins(L)≥0\mathrm{optBins}(L) \ge 0optBins(L)≥0.
  • No junk values. The statement contains no division by a variable, no subtraction of naturals, and no suprema or integrals. The only operations whose behaviour is not visible here are those inside 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