Corollary of Section 2 —
ProvedBinPacking.FirstFit.ratio_limit_eqFor let (respectively ) be the largest value of the ratio (respectively ) over all lists of reals in with . Then
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 more bins than necessary, and for both there are lists on which it does use about more.
Formalization Note and are suprema in the extended nonnegative reals and the limit is taken there, so the statement asserts both that the ratios are eventually at most and that they eventually exceed .
import Mathlib import Definitions.Def_BinPacking_FirstFit_Model
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
The two quantities in this statement, (written ratioFF) and (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 , indexed by a type with an "eventually, for all large " filter (presumably the natural numbers ). Its values lie in the extended non-negative reals , which includes .
The documentation comment describes and this way: take all item lists whose optimum bin count is , and take the supremum of (First Fit) or (Best Fit) over those lists, computed in . 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, , and are modelled, has to be checked against that module.
The declaration asserts both of the following. No hypotheses or extra variables are involved.
- converges to :
- converges to :
Both limits are taken in the usual topology of . Here is the ordinary finite number , because the denominator is non-zero. Converging to a finite limit in means two things: from some index on, every term is finite, and those finite terms converge to in the usual real sense.
This is a statement about limits only. It says nothing about any individual value for a fixed . In particular, it does not say that , that , or that the sequence is monotone.
Degenerate cases. Because only the tail of each sequence matters, finitely many terms may take any value, including or . Two such cases are possible:
- or small : if the definitions divide by an optimum of (in , a positive number divided by is , and is ), those terms do not affect the claim.
- Empty sets of lists: if some has no admissible list, the supremum over the empty set is in . Such terms do not affect the claim either, as long as only finitely many are affected.
If for infinitely many , or is a junk value from an empty supremum for infinitely many , 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 , the presumed index, that does not occur.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.