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.
翻译:我们证明,在适当的竞争比率标准方面,有两个宽松的在线包装问题:在线可移动的多个宽线背包和最近推出的在线最低峰值约会时间安排问题。这两个问题的高度目标是尽可能高效地将最多1个大小的进货物品包装到1号容量的箱中,但确切的正规化则有所不同。在任命时间安排问题中,每个物品都必须被分配到一个位置上,这可以在一个工作日的长度中被视为一个时间间隔。也就是说,项目不分配给垃圾箱,但只有在所有物品都处理完毕后,才能确定被选定位置的垃圾箱的最佳数量,这是在线算法的成本。另一方面,在可移动的Knapsack问题中,有一个固定的垃圾箱,包装物品的目标,即为每个被包装的物品选择一个特定的垃圾箱(等等),是尽可能有价值的子组。在最后一个问题中,可以拒绝物品,即故意不包装它们,然后在任何较晚的时间将包装物品移走,从而增加了问题的灵活性。