The computational complexity of a bin packing game
Fcr Spieksma, GJ Gerhard Woeginger · TU/e Research Portal · 1994
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.