An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem

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.

Authors

• Narendra Karmarkar
• Richard M. Karp

Keywords

• Polynomials
• Optimized production technology
• Costs
• Linear programming
• Pulp and paper industry
• Ellipsoids
• Approximation algorithms
• One-dimensional Problem
• Bin Packing Problem
• Ellipsoid
• Estimation Algorithm
• Feasible Solution
• Linear Problem
• Basic Solution
• Problem Instances
• Polynomial-time Algorithm
• Fractional Problem
• Knapsack Problem
• Division Operation
• Execution Time Of Algorithm
• Price Vector
• Linear Programming Relaxation
• Column Generation