| Article ID: | iaor2001932 |
| Country: | Slovakia |
| Volume: | 3 |
| Issue: | 1 |
| Start Page Number: | 39 |
| End Page Number: | 50 |
| Publication Date: | Jan 1994 |
| Journal: | Central European Journal of Operations Research |
| Authors: | Woeginger Gerhard J., Spieksma Frits C.R. |
| Keywords: | computational analysis |
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.