Online Unweighted Knapsack Problem with Removal Cost
Online Unweighted Knapsack Problem with Removal Cost
复制标题
在线未称重背包搬运成本问题
DOI：
10.1007/s00453-013-9822-z
复制
发表时间：
2014-09-01
期刊：
影响因子：
1.1
通讯作者：
Makino, Kazuhisa
中科院分区：
文献类型：
--
作者：
Han, Xin;Kawase, Yasushi;Makino, Kazuhisa
本文研究了带移动费用的在线未加权背包问题。输入是一系列项目u（1）、u（2）、a Euro虚线竖条u（n），每个项目都有一个大小和一个值，其中每个项目的值被假设为等于大小。给定第i个物品u（i），我们要么把u（i）放进背包，要么拒绝它而不付出任何代价。当u（i）被放入背包时，如果u（i）的大小与当前背包中的总大小之和超过背包的容量，则背包中的一些物品被移除，并具有移除成本。在这里，搬运费是指取消费或处理费。我们的目标是利润最大化，即，最后一个背包中物品的价值之和减去发生的总迁移成本。2本文考虑了两种迁移成本：单位迁移成本和比例迁移成本。对于这两种型号，我们提供了它们的竞争比率。也就是说，我们构造最优的在线算法，并证明他们是最好的可能。
In this paper, we study the online unweighted knapsack problem with removal cost. The input is a sequence of items u (1),u (2),aEuro broken vertical bar,u (n) , each of which has a size and a value, where the value of each item is assumed to be equal to the size. Given the ith item u (i) , we either put u (i) into the knapsack or reject it with no cost. When u (i) is put into the knapsack, some items in the knapsack are removed with removal cost if the sum of the size of u (i) and the total size in the current knapsack exceeds the capacity of the knapsack. Here the removal cost means a cancellation charge or disposal fee. Our goal is to maximize the profit, i.e., the sum of the values of items in the last knapsack minus the total removal cost occurred.In this paper, we consider two kinds of removal cost: unit and proportional cost. For both models, we provide their competitive ratios. Namely, we construct optimal online algorithms and prove that they are best possible.