Optimal Resource Augmentations for Online Knapsack
Optimal Resource Augmentations for Online Knapsack
复制标题
DOI：
10.1007/978-3-540-74208-1_13
复制
发表时间：
2007-08
期刊：
影响因子：
--
通讯作者：
K. Iwama;Guochuan Zhang
中科院分区：
文献类型：
--
作者：
K. Iwama;Guochuan Zhang
众所周知，在线背包没有竞争力。即使这些物品是可拆卸的，这个否定的结果仍然成立。本文考虑具有资源增强的在线可移动背包，其中我们持有一个容量r≥1.0的背包，并以保持可行的包装为目标，使所装物品的总重量最大化。可以移除已接受的项目，以便为新到达的项目留出空间。一旦一个项目被拒绝/移除，它就不能再被考虑。我们评估一个在线算法通过比较结果的包装与最优包装，使用容量为1的背包。针对加权情况（物品具有任意权重）和未加权情况（物品的重量与其大小相等），导出了最优在线算法。
It is known that online knapsack is not competitive. This negative result remains true even if the items are removable. In this paper we consider online removable knapsack with resource augmentation, in which we hold a knapsack of capacityR≥ 1.0 and aim at maintaining a feasible packing to maximize the total weight of the items packed. Accepted items can be removed to leave room for newly arriving items. Once an item is rejected/removed it can not be considered again. We evaluate an online algorithm by comparing the resulting packing to an optimal packing that uses a knapsack of capacity one. Optimal online algorithms are derived for both the weighted case (items have arbitrary weights) and the un-weighted case (the weight of an item is equal to its size).