One-dimensional Binding Bin-covering Problem

In this thesis, we consider the one-dimensional binding bin-covering problem, it is a new problem based on the one-dimensional bin-covering problem, which is defined as follows:given a list I=(a1,a2,...,an)of n items, and each item ai size as s(ai)∈(0,1], where i=1,2,..., n, and given an inexhaustible supply of K-binding bin with size 1, we are asked to put these n items to cover some K-binding bins, the objective is to maximize the number of the K-binding bins covered, where a K-binding bin is composed of K small bins with size 1, the definition of a K-binding bin covered is the sum of sizes of the items in the each small bin of K-binding bin not less than 1.For the one-dimensional binding bin-covering problem, we design three approxi-mation algorithms to solve this problem, called as K-NF algorithm, K-FFD algorith-m and K-T algorithm, and the asymptotic performance ratios of these algorithms are 2,3/2 and 2, respectively, and the complexity of algorithms are O(n), O(nlogn) and O(n), respectively.