Randomized strategies for cardinality robustness in the knapsack problem
Randomized strategies for cardinality robustness in the knapsack problem
复制标题
背包问题中基数鲁棒性的随机策略
DOI：
10.1137/1.9781611974324.3
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yusuke Kobayashi and Kenjiro Takazawa
中科院分区：
文献类型：
--
作者：
浩日勒;山内聡;工藤大介;仁木敏朗;芦野有悟;服部俊夫;久志本成樹;Hoshi M;Yusuke Kobayashi and Kenjiro Takazawa
我们考虑以下与背包问题相关的零和博弈。在一个背包问题的例子中，Alice选择一个背包解，Bob知道Alice的解，选择基数k，Alice得到的收益等于她的解中最好的k个项目的收益与最大规模k的最佳解的收益之比，当α> 0时，背包解称为α-鲁棒解，如果它保证收益α。如果Alice采用确定性策略，则Alice的目标是找到最大鲁棒背包解。通过应用Kakimura和Makino（2013）关于一般独立系统鲁棒性的论证，在多项式时间内找到了鲁棒解的存在性，其中μ是独立系统的交换矩阵。Matuschke，Skutella和Soto（2015）介绍了鲁棒独立系统中的随机化策略，他们提出了一类具有1/ln（4）-鲁棒性的随机化策略。然而，背包问题不属于这一类。我们首先通过一个例子证明了背包问题的难处理性，使得任意随机策略的鲁棒性都是O（log logμ/logμ）和O（log logρ/logρ），其中.然后，我们通过设计两个分别具有鲁棒性Ω（1/ logμ）和Ω（1/ logρ）的随机化策略来展示随机性的力量，这两个随机化策略大大改善了确定性策略的鲁棒性，并且几乎达到了上述上界。同样值得注意的是，我们的策略不仅适用于背包问题，但也独立系统的基数约束下的（近似）最优解是可计算的。
We consider the following zero-sum game related to the knapsack problem. Given an instance of the knapsack problem, Alice chooses a knapsack solution and Bob, knowing Alice's solution, chooses a cardinalityk.Then, Alice obtains a payoff equal to the ratio of the profit of the bestkitems in her solution to that of the best solution of size at mostk.Forα> 0, a knapsack solution is calledα-robustif it guarantees payoffα. If Alice adopts a deterministic strategy, the objective of Alice is to find a max-robust knapsack solution. By applying the argument in Kakimura and Makino (2013) for robustness in general independence systems, a robust solution exists and is found in polynomial time, whereμis the exchangeability of the independence system.In the present paper, we address randomized strategies for this zero-sum game. Randomized strategies in robust independence systems are introduced by Matuschke, Skutella, and Soto (2015) and they presented a randomized strategy with 1/ln(4)-robustness for a certain class of independence systems. The knapsack problem, however, does not belong to this class. We first establish the intractability of the knapsack problem by showing an instance such that the robustness of an arbitrary randomized strategy is both O(log logμ/logμ) and O(log logρ/logρ), where . We then exhibit the power of randomness by designing two randomized strategies with robustness Ω(1/ logμ) and Ω(1/ logρ), respectively, which substantially improve upon that of deterministic strategies and almost attain the above upper bounds. It is also noteworthy that our strategy applies to not only the knapsack problem but also independence systems for which an (approximately) optimal solution under a cardinality constraint is computable.