
Randomized strategies for cardinality robustness in the knapsack problemRandomized strategies for cardinality robustness in the knapsack problemAA00862688 
"/Kobayashi, Yusuke/"Kobayashi, Yusuke ,
"/Takazawa, Kenjiro/"Takazawa, Kenjiro
699pp.53

62 , 201711 , Elsevier
ISSN:03043975
NCID:AA00862688
Description
We consider the following zerosum 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 maxrobust knapsack solution. By applying the argument in Kakimura and Makino[6]for 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 zerosum game. Randomized strategies in robust independence systems are introduced by Matuschke, Skutella, and Soto[11]and 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.
FullText
https://tsukuba.repo.nii.ac.jp/?action=repository_action_common_download&item_id=44551&item_no=1&attribute_id=17&file_no=1