We consider the product knapsack problem, which is the variant of the classical 0-1 knapsack problem where the objective consists of maximizing the product of the profits of the selected items. These profits are allowed to be positive or negative. We show that this recently introduced variant of the knapsack problem is weakly NP-hard and present a fully polynomial-time approximation scheme (FPTAS) for the problem. Moreover, we analyze the approximation quality achieved by a natural extension of the classical greedy procedure to the product knapsack problem.


翻译:我们认为产品背包问题,这是古典0-1背包问题的变种,其目标包括最大限度地增加选定物品的利润。允许这些利润是正的或负的。我们表明,最近引入的背包问题的变种是微弱的NP-硬化,为问题提出了一个完全多时近似计划(FPTAS ) 。此外,我们分析了通过将传统贪婪程序自然延伸至产品背包问题而实现的近似质量。

0
下载
关闭预览

相关内容

和积网络综述论文,Sum-product networks: A survey,24页pdf
专知会员服务
23+阅读 · 2020年4月3日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
生物探索
3+阅读 · 2018年2月10日
Arxiv
0+阅读 · 2021年8月30日
Arxiv
0+阅读 · 2021年8月25日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
生物探索
3+阅读 · 2018年2月10日
Top
微信扫码咨询专知VIP会员