||Randomized strategies for cardinality robustness in the knapsack problem
Kobayashi, YusukeTakazawa, Kenjiro
Theoretical computer science
62 , 2017-11 , Elsevier
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 best kitems in her solution to that of the best solution of size at most k. 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 Makinofor robustness in general independence systems, a (1/√μ)-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. Random-ized strategies in robust independence systems are introduced by Matuschke, Skutella, and Sotoand they presented a randomized strategy with (1/ ln4)-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((loglogμ)/ logμ)and O((loglogρ)/ logρ), where ρ:=(thesizeofamaximumfeasibleset)(thesizeofaminimuminfeasibleset)−1. 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 known 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.