One-dimensional Binding Bin-packing Problem

We generalize one-dimensional bin-packing problem, and then propose a new problem, where we call the new problem as the one-dimensional binding bin-packing problem. The new problem is defined as follows:given a list I= (a1,a2,...,an) of n items, each item a* with size s(ai) e (0,l], where i = 1,2,...,n, and given an inexhaustible supply of K-binding bins, we are asked to put these n items into some K-binding bins, and the sum of sizes of the items in each small bin of the K-binding bin can not exceed l, the objective is to minimize the numbers of the K-binding bins used, where a K-binding bin is bound together by K bins of size l, the size of the K-binding bin is l.For one-dimensional binding bin packing problem in the off-line version, we de-sign three approximation algorithms, i.e., K-NF algorithm, K-FFD algorithm and K-SFOF algorithm, where approximation ratio of K-NF algorithm is 2, its com-plexity is O(n);asymptotic approximation ratios of K-FFD algorithm and K-SFOF algorithm are 3/2, and their complexities are respectively O(n2) and O(n). And For one-dimensional binding bin packing problem in the on-line version, we design one asymptotic approximation algorithm, i.e., K-SFON algorithm, its asymptotic approximation ratio is 7/4 and its complexity is O(n).