Randomized strategies for cardinality robustness in the knapsack problem

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 [11] 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 ρ:=(the size of a maximum feasible set)(the size of a minimum infeasible set)−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.