Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary of Section 2 — lim⁡k→∞RFF(k)=lim⁡k→∞RBF(k)=1.7\lim_{k\to\infty}R_{FF}(k)=\lim_{k\to\infty}R_{BF}(k)=1.7limk→∞​RFF​(k)=limk→∞​RBF​(k)=1.7

Proved
BinPacking.FirstFit.ratio_limit_eq

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

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

For k≥1k\ge 1k≥1 let RFF(k)R_{FF}(k)RFF​(k) (respectively RBF(k)R_{BF}(k)RBF​(k)) be the largest value of the ratio FF(L)/L∗FF(L)/L^*FF(L)/L∗ (respectively BF(L)/L∗BF(L)/L^*BF(L)/L∗) over all lists LLL of reals in (0,1](0,1](0,1] with L∗=kL^*=kL∗=k. Then

lim⁡k→∞RFF(k)=1.7andlim⁡k→∞RBF(k)=1.7.\lim_{k\to\infty}R_{FF}(k)=1.7\qquad\text{and}\qquad\lim_{k\to\infty}R_{BF}(k)=1.7.k→∞lim​RFF​(k)=1.7andk→∞lim​RBF​(k)=1.7.

This is the asymptotic worst-case performance ratio of First-Fit and Best-Fit: on lists with large optimum, neither algorithm ever uses more than about 70%70\%70% more bins than necessary, and for both there are lists on which it does use about 70%70\%70% more.

Formalization Note RFF(k)R_{FF}(k)RFF​(k) and RBF(k)R_{BF}(k)RBF​(k) are suprema in the extended nonnegative reals [0,∞][0,\infty][0,∞] and the limit is taken there, so the statement asserts both that the ratios are eventually at most 1.7+ε1.7+\varepsilon1.7+ε and that they eventually exceed 1.7−ε1.7-\varepsilon1.7−ε.

Preamble
import Mathlib
import Definitions.Def_BinPacking_FirstFit_Model
Formal statement
namespace BinPacking.FirstFit

/-- Corollary of Section 2 (p. 306): (i) `lim_{k→∞} R_FF(k) = 1.7` and
(ii) `lim_{k→∞} R_BF(k) = 1.7`, where `R_FF(k)`, `R_BF(k)` are the suprema of `FF(L)/L*`,
`BF(L)/L*` over all lists with `L* = k`, taken in `ℝ≥0∞`. -/
theorem ratio_limit_eq :
    Filter.Tendsto ratioFF Filter.atTop (nhds ((17 : ENNReal) / 10)) ∧
    Filter.Tendsto ratioBF Filter.atTop (nhds ((17 : ENNReal) / 10)) := by sorry

end BinPacking.FirstFit
Source
Johnson, Demers, Ullman, Garey, Graham, Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms, SIAM J. Comput. 3(4) (1974), p. 306, Corollary of Section 2 (after Theorem 2.2)
Read-back

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

The two quantities in this statement, RFFR_{\mathrm{FF}}RFF​ (written ratioFF) and RBFR_{\mathrm{BF}}RBF​ (written ratioBF), are defined in the imported module Definitions.Def_BinPacking_FirstFit_Model. That module was not part of the code I was given, so I can't unfold them. The statement only fixes their type: each is a sequence k↦R(k)k \mapsto R(k)k↦R(k), indexed by a type with an "eventually, for all large kkk" filter (presumably the natural numbers N\mathbb{N}N). Its values lie in the extended non-negative reals [0,∞][0,\infty][0,∞], which includes +∞+\infty+∞.

The documentation comment describes RFF(k)R_{\mathrm{FF}}(k)RFF​(k) and RBF(k)R_{\mathrm{BF}}(k)RBF​(k) this way: take all item lists LLL whose optimum bin count is L∗=kL^* = kL∗=k, and take the supremum of FF(L)/L∗\mathrm{FF}(L)/L^*FF(L)/L∗ (First Fit) or BF(L)/L∗\mathrm{BF}(L)/L^*BF(L)/L∗ (Best Fit) over those lists, computed in [0,∞][0,\infty][0,∞]. That is the author's description, not something the code shown here asserts. Whether the imported definitions actually compute this, including how "list", "bin", item sizes, capacity, FF\mathrm{FF}FF, BF\mathrm{BF}BF and L∗L^*L∗ are modelled, has to be checked against that module.

The declaration asserts both of the following. No hypotheses or extra variables are involved.

  1. RFFR_{\mathrm{FF}}RFF​ converges to 1710\tfrac{17}{10}1017​:
lim⁡k→∞RFF(k)=1710.\lim_{k\to\infty} R_{\mathrm{FF}}(k) = \tfrac{17}{10}.k→∞lim​RFF​(k)=1017​.
  1. RBFR_{\mathrm{BF}}RBF​ converges to 1710\tfrac{17}{10}1017​:
lim⁡k→∞RBF(k)=1710.\lim_{k\to\infty} R_{\mathrm{BF}}(k) = \tfrac{17}{10}.k→∞lim​RBF​(k)=1017​.

Both limits are taken in the usual topology of [0,∞][0,\infty][0,∞]. Here 1710\tfrac{17}{10}1017​ is the ordinary finite number 1.71.71.7, because the denominator 101010 is non-zero. Converging to a finite limit in [0,∞][0,\infty][0,∞] means two things: from some index on, every term is finite, and those finite terms converge to 1.71.71.7 in the usual real sense.

This is a statement about limits only. It says nothing about any individual value R(k)R(k)R(k) for a fixed kkk. In particular, it does not say that R(k)≤1.7R(k) \le 1.7R(k)≤1.7, that R(k)≥1.7R(k) \ge 1.7R(k)≥1.7, or that the sequence is monotone.

Degenerate cases. Because only the tail of each sequence matters, finitely many terms may take any value, including +∞+\infty+∞ or 000. Two such cases are possible:

  • k=0k = 0k=0 or small kkk: if the definitions divide by an optimum of 000 (in [0,∞][0,\infty][0,∞], a positive number divided by 000 is +∞+\infty+∞, and 0/00/00/0 is 000), those terms do not affect the claim.
  • Empty sets of lists: if some kkk has no admissible list, the supremum over the empty set is 000 in [0,∞][0,\infty][0,∞]. Such terms do not affect the claim either, as long as only finitely many kkk are affected.

If R(k)=+∞R(k) = +\inftyR(k)=+∞ for infinitely many kkk, or R(k)R(k)R(k) is a junk value 000 from an empty supremum for infinitely many kkk, the stated limit would be false. The statement therefore implicitly asserts that neither happens.

If the index type were empty, the "eventually" filter would be trivial and the claim vacuous. With N\mathbb{N}N, the presumed index, that does not occur.

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