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

摘要

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