Approximate core allocation for binpacking games

Ulrich Faigle, Walter Kern

    Research output: Contribution to journalArticleAcademicpeer-review

    19 Citations (Scopus)
    8 Downloads (Pure)


    A binpacking game is a cooperative N-person game, where the set of players consists of k bins of size 1 and n items of sizes a1,..., an. The value of a coalition of bins and items is the maximum total size of items in the coalition that can be packed into the bins of the coalition. Our main result asserts that for every $\epsilon > 0$, there exist $\epsilon$-approximate core allocations provided k is large enough. Moreover, for every fixed $\delta > 0$, the smallest $\epsilon$ for which the $\epsilon$-approximate core of a given binpacking game is nonempty can be computed in polynomial time with error at most $\delta$, provided k is sufficiently large. We furthermore derive more specialized results for some subclasses of binpacking games.
    Original languageEnglish
    Pages (from-to)387-399
    Number of pages13
    JournalSIAM journal on discrete mathematics
    Issue number3
    Publication statusPublished - 1998


    Dive into the research topics of 'Approximate core allocation for binpacking games'. Together they form a unique fingerprint.

    Cite this