Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4 — ALGORITHM 2 with k=2k=2k=2, g=1/SIZE(I)g = 1/SIZE(I)g=1/SIZE(I) packs within OPT(I)+O(log⁡2OPT(I))OPT(I) + O(\log^2 OPT(I))OPT(I)+O(log2OPT(I)) bins

Proved
KKBinPacking.GeometricGrouping.algorithm2_log_squared_bound

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

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

Let III be an instance of the one-dimensional bin-packing problem with SIZE(I)≥2SIZE(I) \ge 2SIZE(I)≥2, and run ALGORITHM 2 with parameters k=2k = 2k=2 and g=1/SIZE(I)g = 1/SIZE(I)g=1/SIZE(I). Every packing PPP it can output is a packing of III, and its number of bins A(I)=∣P∣A(I) = |P|A(I)=∣P∣ satisfies

A(I)≤OPT(I)+(1+log⁡2OPT(I))(9+4ln⁡OPT(I))+2+4ln⁡OPT(I).A(I) \le OPT(I) + \bigl(1 + \log_2 OPT(I)\bigr)\bigl(9 + 4\ln OPT(I)\bigr) + 2 + 4\ln OPT(I).A(I)≤OPT(I)+(1+log2​OPT(I))(9+4lnOPT(I))+2+4lnOPT(I).

In particular A(I)≤OPT(I)+O(log⁡2OPT(I))A(I) \le OPT(I) + O(\log^2 OPT(I))A(I)≤OPT(I)+O(log2OPT(I)): the additive error of this algorithm grows only polylogarithmically in the optimum.

Formalization Note The paper writes A(I)≤OPT(I)+O(log⁡2OPT(I))A(I) \le OPT(I) + O(\log^2 OPT(I))A(I)≤OPT(I)+O(log2OPT(I)); its proof, the general bound for ALGORITHM 2 with k=2k = 2k=2 and g=1/SIZE(I)g = 1/SIZE(I)g=1/SIZE(I) together with SIZE(I)≤OPT(I)SIZE(I) \le OPT(I)SIZE(I)≤OPT(I) (Lemma 2) and OPT(I)≤2 SIZE(I)+1OPT(I) \le 2\,SIZE(I)+1OPT(I)≤2SIZE(I)+1 (Lemma 1), yields the explicit constants stated here. The hypothesis SIZE(I)≥2SIZE(I) \ge 2SIZE(I)≥2 makes the paper's asymptotic threshold explicit: Lemma 3 is applied with parameter 2g=2/SIZE(I)2g = 2/SIZE(I)2g=2/SIZE(I), which must be at most 111, and for SIZE(I)<e−1/2SIZE(I) < e^{-1/2}SIZE(I)<e−1/2 the while loop of ALGORITHM 2 with g=1/SIZE(I)g = 1/SIZE(I)g=1/SIZE(I) 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: ln⁡\lnln is Real.log, log⁡2\log_2log2​ is Real.logb 2.

Preamble
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
Formal statement
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
Source
Karmarkar, Karp, An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem, Proc. 23rd FOCS, 1982, p. 317, Theorem 4 (left column), with the display "Hence by Lemma 3" at k = 2, g = 1/SIZE(I)
Human review
  • Endorsed by Shuze Chen · Oct 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 1, 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