论文标题
关于放松包装问题的在线算法性能的下限
Lower bounds on the performance of online algorithms for relaxed packing problems
论文作者
论文摘要
我们证明了两个放松的在线包装问题的合适竞争比率度量：在线可移动多重背包以及最近引入的在线最低峰值约会计划问题。这两个问题的高度目标是将最多1个大小的物品包装到容量1的垃圾箱中，尽可能有效，但确切的形式化有所不同。在约会计划问题中，每个项目都必须分配给一个位置，该位置可以看作是长度为1的工作时间间隔。也就是说，只有将所有项目分配给垃圾箱，但是只有在处理所有项目后，就可以确定所有项目，即确定所选位置的最佳垃圾箱数量，并且这是在线algorithm的成本。另一方面，在可移动的背包问题中，有固定数量的垃圾箱，包装物品的目标是为每个包装物品选择一个特定的垃圾箱（以及其他任何内容），就是打包尽可能有价值的子集。在最后一个问题中，有可能拒绝项目，也就是说，故意不要打包它们，并在任何以后的时间点删除包装的项目，从而为问题增加了灵活性。
We prove new lower bounds for suitable competitive ratio measures of two relaxed online packing problems: online removable multiple knapsack, and a recently introduced online minimum peak appointment scheduling problem. The high level objective in both problems is to pack arriving items of sizes at most 1 into bins of capacity 1 as efficiently as possible, but the exact formalizations differ. In the appointment scheduling problem, every item has to be assigned to a position, which can be seen as a time interval during a workday of length 1. That is, items are not assigned to bins, but only once all the items are processed, the optimal number of bins subject to chosen positions is determined, and this is the cost of the online algorithm. On the other hand, in the removable knapsack problem there is a fixed number of bins, and the goal of packing items, which consists in choosing a particular bin for every packed item (and nothing else), is to pack as valuable a subset as possible. In this last problem it is possible to reject items, that is, deliberately not pack them, as well as to remove packed items at any later point in time, which adds flexibility to the problem.
