论文标题
在线简单的背包与预订成本
Online Simple Knapsack with Reservation Costs
论文作者
论文摘要
在在线简单的背包中，问题项目以迭代方式呈现，并且算法必须为每个项目决定是否拒绝或永久将其纳入主背包，而无需对实例的其余部分了解。目标是将背包装满尽可能饱的。在这项工作中，我们介绍了保留物品的选项，以固定的分数$α$的尺寸成本。算法可以支付此分数，以便将其决定是否包括或拒绝这些项目进行决定，直到实例的最后一项出现后。 虽然经典的在线简单背包问题在确定性的环境中并未承认任何不断限制的竞争比率，但我们发现添加预订的可能性使问题不断竞争。我们的$α$从$ 0 $到$ 1 $的整个范围都进行了紧密的界限。
In the online simple knapsack problem items are presented in an iterative fashion and an algorithm has to decide for each item whether to reject or permanently include it into the knapsack without any knowledge about the rest of the instance. The goal is to pack the knapsack as full as possible. In this work, we introduce the option of reserving items for the cost of a fixed fraction $α$ of their size. An algorithm may pay this fraction in order to postpone its decision on whether to include or reject these items until after the last item of the instance was presented. While the classical online simple knapsack problem does not admit any constantly bounded competitive ratio in the deterministic setting, we find that adding the possibility of reservation makes the problem constantly competitive. We give tight bounds for the whole range of $α$ from $0$ to $1$.
