Theorem 3.2 — and for all lists
ProvedBinPacking.Decreasing.ffd_bfd_le_eleven_ninthsLet be any list of real numbers in , and let 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 bins:
Together with the matching lower bound (Theorem 3.1) this gives the asymptotic worst-case ratio of the two decreasing heuristics, the headline result of the paper.
Formalization Note and are computed on arranged into nonincreasing order by the mission's sort; the statement holds for every list , sorted or not. The constants and are exactly the paper's.
import Mathlib import Definitions.Def_BinPacking_Decreasing_Model
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
For every finite list of real numbers that satisfies the predicate , both of the following hold together:
Symbols.
- is an ordered list of reals. It may contain repeated entries, and the order of its entries is part of the input.
- is the only hypothesis.
- , and are three quantities that depend on . Each is converted to a real number before the comparison, so each takes values in a number type that embeds in , most likely the natural numbers.
- All arithmetic in the inequalities is ordinary real arithmetic. The constant is the exact rational , and the additive constant is exactly .
- The two inequalities are joined by "and". The same list must satisfy both.
What could not be unfolded. The four names , , and 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 requires the entries to lie in , or requires anything at all;
- that and are the numbers of bins used by the First-Fit-Decreasing and Best-Fit-Decreasing heuristics;
- that is the minimum number of unit-capacity bins that can hold .
The attached comment mentions "Theorem 3.2 (p. 308)" and entries in . 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 (): the claim covers it whenever holds for the empty list. It then says and of the empty list are each at most . If of the empty list is , the bound becomes .
- One-element list: it is covered in the same way, with no special treatment.
- Additive slack: because of the , any list whose and values are at most satisfies the claim no matter what is.
- Junk values: if gives a default value on some inputs, such as for an infimum over an empty set, the bound is checked against that value exactly as returned. The same applies if or return default values, for example when an entry exceeds bin capacity.
- Vacuous or overly broad hypothesis: if 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.