Sparse near-optimal configuration LP solutions
ProvedKKBinPacking.GeometricGrouping.exists_sparse_near_optimal_lpapproximation-algorithmsbin-packinglinear-programming
Let be a finite bin-packing instance with real item sizes in , let be its number of distinct sizes, and let be the infimum of the configuration-LP objective. For every , there is a nonnegative feasible configuration vector such that
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