Theorem 4 — ALGORITHM 2 with , packs within bins
ProvedKKBinPacking.GeometricGrouping.algorithm2_log_squared_boundLet be an instance of the one-dimensional bin-packing problem with , and run ALGORITHM 2 with parameters and . Every packing it can output is a packing of , and its number of bins satisfies
In particular : the additive error of this algorithm grows only polylogarithmically in the optimum.
Formalization Note The paper writes ; its proof, the general bound for ALGORITHM 2 with and together with (Lemma 2) and (Lemma 1), yields the explicit constants stated here. The hypothesis makes the paper's asymptotic threshold explicit: Lemma 3 is applied with parameter , which must be at most , and for the while loop of ALGORITHM 2 with never terminates. The bound holds for every run of the algorithm (every output of the Fractional Bin-Packing subroutine within its contract, every admissible packing at Steps 2 and 3, every run of the Step 4 insertion). The statements about running time and the number of subroutine calls are not formalized. Logarithms: is Real.log, is Real.logb 2.
import Mathlib import Definitions.Def_KKBinPacking_GeometricGrouping_Instance import Definitions.Def_KKBinPacking_Shared_ConfigLP import Definitions.Def_KKBinPacking_Shared_AnyFit import Definitions.Def_KKBinPacking_GeometricGrouping_GeomGroup import Definitions.Def_KKBinPacking_GeometricGrouping_Algorithm2 open KKBinPacking.Shared
namespace KKBinPacking.GeometricGrouping
theorem algorithm2_log_squared_bound (I : Multiset ℝ) (hI : IsInstance I) (hS : 2 ≤ SIZE I)
(P : Multiset (Multiset ℝ)) (hP : Alg2Run 2 (1 / SIZE I) I P) :
IsPacking I P ∧
(Multiset.card P : ℝ) ≤
(OPT I : ℝ) + (1 + Real.logb 2 (OPT I)) * (9 + 4 * Real.log (OPT I)) +
2 + 4 * Real.log (OPT I) := by sorry
end KKBinPacking.GeometricGrouping
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.