...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematics of Operations Research >Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
【24h】

Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity

机译：近似随机背包问题：适应性的好处

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

摘要

We consider a stochastic variant of the NP-hard 0/1 knapsack problem, in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. Our goal is to compute a solution "policy" that maximizes the expected value of items successfully placed in the knapsack, where the final overflowing item contributes no value. We consider both nonadaptive policies (that designate a priori a fixed sequence of items to insert) and adaptive policies (that can make dynamic choices based on the instantiated sizes of items placed in the knapsack thus far). An important facet of our work lies in characterizing the benefit of adaptivity. For this purpose we advocate the use of a measure called the adaptivity gap: the ratio of the expected value obtained by an optimal adaptive policy to that obtained by an optimal nonadaptive policy. We bound the adaptivity gap of the stochastic knapsack problem by demonstrating a polynomial-time algorithm that computes a nonadaptive policy whose expected value approximates that of an optimal adaptive policy to within a factor of four. We also devise a polynomial-time adaptive policy that approximates the optimal adaptive policy to within a factor of 3 + for any constant > 0.
机译：我们考虑NP-hard 0/1背包问题的随机变体，其中物品的值是确定性的，物品的大小是具有已知任意分布的独立随机变量。将项目顺序放置在背包中，将项目放置在背包中的操作会实例化其大小。我们的目标是计算一种解决方案“策略”，以最大程度地将成功放置在背包中的物品的期望值最大化，其中最终溢出的物品没有任何价值。我们同时考虑非自适应策略（先指定要插入的固定序列的先验序列）和自适应策略（可以根据到目前为止放置在背包中的实例化大小进行动态选择）。我们工作的一个重要方面在于表征适应性的好处。为此，我们提倡使用一种称为适应性差距的措施：一种最佳适应策略获得的期望值与最佳非适应策略获得的期望值之比。我们通过演示一种多项式时间算法来限制随机背包问题的适应性差距，该算法计算期望值与最佳适应性策略的期望值接近四倍的非适应性策略。我们还设计了多项式时间自适应策略，对于任何常数> 0，该策略都将最佳自适应策略近似在3 +以内。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号