Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sparse near-optimal configuration LP solutions

Proved
KKBinPacking.GeometricGrouping.exists_sparse_near_optimal_lp

by Yuxuan Xu · Oct 2, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsbin-packinglinear-programming

Let III be a finite bin-packing instance with real item sizes in (0,1)(0,1)(0,1), let m(I)m(I)m(I) be its number of distinct sizes, and let LIN(I)LIN(I)LIN(I) be the infimum of the configuration-LP objective. For every ε>0\varepsilon>0ε>0, there is a nonnegative feasible configuration vector xxx such that

∑cxc<LIN(I)+ε,∣supp⁡(x)∣≤m(I).\sum_c x_c < LIN(I)+\varepsilon, \qquad |\operatorname{supp}(x)|\le m(I).c∑​xc​<LIN(I)+ε,∣supp(x)∣≤m(I).

This isolates the finite-dimensional LP sparsity ingredient of the additive rounding bound. It is the consequence of the optimal basic feasible solution used in the source, expressed at arbitrary positive tolerance so that later deductions do not assume infimum attainment separately. Near-optimality and the support bound are both required, including for the empty instance.

Preamble
import Definitions.Def_KKBinPacking_GeometricGrouping_Instance
import Definitions.Def_KKBinPacking_Shared_ConfigLP
open KKBinPacking.Shared
Formal statement
namespace KKBinPacking.GeometricGrouping
theorem exists_sparse_near_optimal_lp
    (I : Multiset ℝ) (hI : IsInstance I) (ε : ℝ) (hε : 0 < ε) :
    ∃ x : Multiset ℝ →₀ ℝ,
      IsLPFeasible I x ∧ lpCost x < LIN I + ε ∧
      x.support.card ≤ numSizes I := by sorry
end KKBinPacking.GeometricGrouping
Source
Karmarkar and Karp, An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem, FOCS 1982, p. 313, Lemma 2, proof of the additive upper bound. https://pagesperso.g-scop.grenoble-inp.fr/~newmana/OptApproxFall2016/Karmarker-Karp-BinPacking.pdf

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