The computational complexity of a bin packing game

F.C.R. Spieksma, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review


    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.
    Original languageEnglish
    Pages (from-to)39-49
    JournalCentral European Journal for Operations Research and Economics
    Issue number1
    Publication statusPublished - 1994


    Dive into the research topics of 'The computational complexity of a bin packing game'. Together they form a unique fingerprint.

    Cite this