Abstract In this paper we investigate the following game: two players I and II must alternately pack items into two equal-sized bins. In one variant, the first player who is not able to move loses the game, in the other variant, player I wins the game if and only if the game ends with all items packed. We show that for both variants the problem of deciding which player has a winning strategy is PSPACE-complete. We also give polynomial time results for some special cases of the problem. Keywords: Bin Packing; Computational Complexity; Game.
|Journal||Central European Journal for Operations Research and Economics|
|Publication status||Published - 1994|