On the Robust Knapsack Problem
On the Robust Knapsack Problem
复制标题
关于鲁棒背包问题
DOI：
--
复制
发表时间：
2013
影响因子：
3.1
通讯作者：
U. Pferschy
中科院分区：
文献类型：
--
作者：
M. Monaci;U. Pferschy
我们考虑背包问题的一种不确定变体，当每个物品的确切重量事先并不确切知道，但属于给定的区间，并且重量与标称值不同的物品的数量由一个常数限定时，该背包问题就产生了。我们分析了最优解相对于经典问题的恶化，并准确地确定了它在所有参数配置下依赖于不确定性的最坏性能。我们对问题的分数版本执行相同的分析，在该版本中，一个人被允许打包任何分数的物品。此外，对于分数阶问题和著名的贪婪算法的一个变种，我们都得到了最坏情况下的性能比。最后，我们考虑了一个相关的特殊情况，并给出了一个有效地解决分数次问题的组合算法。
We consider an uncertain variant of the knapsack problem that arises when the exact weight of each item is not exactly known in advance but belongs to a given interval, and the number of items whose weight differs from the nominal value is bounded by a constant. We analyze the worsening of the optimal solution value with respect to the classical problem, and exactly determine its worst-case performance depending on uncertainty for all parameter configurations. We perform the same analysis for the fractional version of the problem in which one is allowed to pack any fraction of the items. In addition, we derive the worst-case performance ratio with respect to the optimal solution value, for both the fractional problem and for a variant of the well-known greedy algorithm. Finally, we consider a relevant special case and provide a combinatorial algorithm for solving the fractional problem in an efficient way.