• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature
【24h】

The benefit of adaptivity in the stochastic knapsack problem with dependence on the state of nature

机译：适应性的好处在于依赖自然状态的随机背包问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider a stochastic variant of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are random variables with known arbitrary distributions. These distributions depend on a common random variable θ denoting the state of the nature. We assume that if we fix a value of θ, then the size variables are independent. So θ induces a limited dependency among the sizes of different items. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. The goal is to compute a policy that maximizes the expected value of items successfully placed in the knapsack, where the final overflowing item contributes no value. We consider both non-adaptive policies (that designate a priori a fixed permutation of items to insert) and adaptive policies (that can make dynamic decisions based on the instantiated sizes of items placed in the knapsack thus far). Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy. We study this measure as a function of the cardinality of the support of θ. Assuming that the support of θ has at most k values, we show a lower bound of Ω(k) and an upper bound of O(k) on the adaptivity gap in our model. We also introduce Ω(lnk) lower bound and O(lnk) upper bound for the case, where the following two additional assumptions hold. The first assumption is stochastic monotonicity of the sizes in terms of θ and the second is that the prior distribution of θ is uniform. We show that both assumptions are vital, i.e., one assumption without the other does not bring us to a sub-linear adaptivity gap. We further show that in the last O(lnk) upper bound on the price of adaptivity we cannot replace the assumption of stochastic monotonicity with the weaker assumption that the item sizes are positively correlated.
机译：我们考虑NP-hard 0/1背包问题的随机变体，其中项目值是确定性的，项目大小是具有已知任意分布的随机变量。这些分布取决于表示自然状态的公共随机变量θ。我们假设如果固定一个θ值，那么大小变量是独立的。因此，θ在不同项目的大小之间产生了有限的依赖性。将项目顺序放置在背包中，将项目放置在背包中的操作会实例化其大小。目标是计算一种策略，以使成功放置在背包中的物品的预期价值最大化，而最终溢出的物品则没有任何价值。我们同时考虑非自适应策略（先指定要插入的项目的固定排列的先验）和自适应策略（可以根据到目前为止放置在背包中的项目的实例化大小做出动态决策）。我们的工作体现了适应性的好处。为此，我们使用一种称为适应性差距的措施：最优适应策略获得的期望值与最优非适应策略获得的期望值之比的实例上的最高点。我们根据θ的支持度的基数来研究此度量。假设θ的支持最多具有k个值，我们在模型的适应性差距上显示Ω（k）的下限和O（k）的上限。对于以下情况，我们还引入了Ω（lnk）下限和O（lnk）上限的情况，以下两个附加假设成立。第一个假设是以θ为单位的大小的随机单调性，第二个假设是θ的先验分布是均匀的。我们证明这两个假设都是至关重要的，即一个假设没有另一个假设不会使我们陷入亚线性适应性差距。我们进一步表明，在适应性价格的最后一个O（lnk）上限中，我们不能用较弱的假设（即项目大小呈正相关关系）代替随机单调性假设。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号