带拒绝箱覆盖问题的局内算法

作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题.设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用.物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱.如果物品被放入箱中,则产生费用.该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景.给出一个求解该问题的局内近似算法C-FF,分析其最坏情况渐近性能比为1/2,并给出了相应的实验结果.

On-line Bin Covering Problem with Rejection

As the extension of bin covering problem(BCP),a bin covering problem with rejection is proposed in this paper,in which n items are given,each with a capacity and cost,and unlimited bins with equal capacity.An item can be either put in one of the bins,in which case we pay its cost,or rejected.Each item is assigned to no more than one bin,the sum of the capacity of the items assigned to the bin is at least the bin's capacity.The objective is to minimize the total cost of the items that are assigned to the bin.This is a new combinatorial optimization problem which has many applications such as and management information on web servers.An online approximation algorithm C-FF is presented to solve this problem.It is proved that the C-FF algorithm has an asymptotic performance ratio of 1/2,finally the experimental results are given.