An online partially fractional knapsack problem
An online partially fractional knapsack problem
复制标题
DOI：
10.1109/ispan.2005.19
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
J. Noga;Veerawan Sarbua
中科院分区：
文献类型：
--
作者：
J. Noga;Veerawan Sarbua
背包问题可以并且已经被用来建模许多资源共享问题。将一部分资源分配给特定代理对系统有好处，但也会阻止其他代理使用这部分资源。对于一个在做出任何决策之前已知代理数量以及每个代理的需求和潜在收益的问题，可以计算出最优分配及其值。在许多情况下，这些价值最初是不知道的，只是随着时间的推移才学会的。当一个问题需要在获得所有可用信息之前做出决定时，通常采用在线算法和竞争分析。在本文中，我们提出了一个在线版本的背包问题，为模型提供了一些证明，给出了确定性情况下问题的确切竞争比，并给出了随机情况下竞争比的界。
The knapsack problem can and has been used to model many resource sharing problems. The allocation of a portion of a resource to a particular agent provides a benefit to the system, but also blocks other agents from utilizing that portion of the resource. For a problem where the number of agents as well as each agent's demand and potential benefit are known prior to any decision being made, the optimal allocation and its value can be calculated. In many situations these values are not known initially, but only learned over time. Online algorithms and competitive analysis are often employed when a problem requires decisions to be made prior to having all information available. In this paper we suggest an online version of the knapsack problem, provide some justification for the model, give the exact competitive ratio for the problem in the deterministic case, and provide bounds on the competitive ratio in the randomized case.