Note on non-uniform bin packing games

Walter Kern, X. Qui

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
18 Downloads (Pure)

Abstract

A non-uniform bin packing game is an $N$-person cooperative game, where the set $N$ is defined by $k$ bins of capacities $b_1,...,b_k$ and $n$ items of sizes $a_1,...,a_n$. The objective function vv of a coalition is the maximum total value of the items of that coalition which can be packed to the bins of that coalition. We investigate the taxation model of Faigle and Kern (1993) [2] and show that the 1/2-core is always nonempty for such bin packing games. If all items have size strictly larger than 1/3, we show that the 5/12-core is always non-empty. Finally, we investigate the limiting case $k\rightarrow\infty$, thereby extending the main result in Faigle and Kern (1998) [3] to the non-uniform case.
Original languageEnglish
Pages (from-to)175-184
Number of pages10
JournalDiscrete applied mathematics
Volume165
DOIs
Publication statusPublished - 11 Mar 2014

Keywords

  • MSC-91A12

Fingerprint Dive into the research topics of 'Note on non-uniform bin packing games'. Together they form a unique fingerprint.

  • Cite this