...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Optimization >A successive approximation algorithm for the multiple knapsack problem
【24h】

A successive approximation algorithm for the multiple knapsack problem

机译：多背包问题的逐次逼近算法

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

摘要

It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.
机译：众所周知，多重背包问题是NP难题，即使两个相同的背包也不允许FPTAS。然而，对于只有一个背包的0-1背包问题已经进行了深入研究，并且存在一些有效的精确或近似算法。解决多个背包问题的一种自然方法是通过使用针对0-1背包问题的有效算法来连续打包背包。本文考虑了一种将背包按其容量的不降序排列的近似算法。我们通过最坏情况分析方法针对2个和3个背包问题分析了该算法，并给出了所有误差范围。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号