×

The computational complexity of a bin packing game. (English) Zbl 0966.91012

Summary: 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.

MSC:

91A46 Combinatorial games
91A12 Cooperative games
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite