In this paper we propose an improved approximation scheme for the Vector Bin Packing problem (VBP), based on the combination of (near-)optimal solution of the Linear Programming (LP) relaxation and a greedy (modified first-fit) heuristic. The Vector Bin Packing problem of higher dimension (d 2) is not known to have asymptotic polynomial-time approximation schemes (unless P = NP). Our algorithm improves over the previously-known guarantee of (ln d + 1 + epsilon) by [1] for higher dimensions (d > 2). We provide a (1) approximation scheme for certain set of inputs for any dimension d. More precisely, we provide a 2-OPT algorithm, a result which is irrespective of the number of dimensions d.
For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive e, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L) L*≦1+e for anyL providedL* is sufficiently large. 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 e, and produces as output a packing using as most (1 + e) OPT(I) + O(e-2) bins. Its execution time is O(e-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.