An efficient approximation scheme for the one-dimensional bin-packing problem

TLDR

The LP relaxation of bin packing was efficiently solved in practice by Gilmore and Gomory. We present several polynomial‑time approximation algorithms for the one‑dimensional bin‑packing problem. These algorithms use a subroutine that solves a linear‑programming relaxation, making at most O(log n) calls and running in O(n log n) time overall. We provide polynomial‑time algorithms with additive O(log OPT) and O(log m) bounds, a (1+ε)–approximation scheme running in O(ε⁻c n log n) time, and prove that the LP relaxation is solvable in polynomial time, establishing the best asymptotic performance bounds to date.

Abstract

We present several polynomial-time approximation algorithms for the one-dimensional bin-packing problem. using a subroutine to solve a certain linear programming relaxation of the problem. Our main results are as follows: There is a polynomial-time algorithm A such that A(I) ≤ OPT(I) + O(log2 OPT(I)). There is a polynomial-time algorithm A such that, if m(I) denotes the number of distinct sizes of pieces occurring in instance I, then A(I) ≤ OPT(I) + O(log2 m(I)). There is an approximation scheme which accepts as input an instance I and a positive real number ε, and produces as output a packing using as most (1 + ε) OPT(I) + O(ε-2) bins. Its execution time is O(ε-c n log n), where c is a constant. These are the best asymptotic performance bounds that have been achieved to date for polynomial-time bin-packing. Each of our algorithms makes at most O(log n) calls on the LP relaxation subroutine and takes at most O(n log n) time for other operations. The LP relaxation of bin packing was solved efficiently in practice by Gilmore and Gomory. We prove its membership in P, despite the fact that it has an astronomically large number of variables.