TY - JOUR
T1 - Note on non-uniform bin packing games
AU - Kern, Walter
AU - Qui, X.
N1 - 10th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2011)
PY - 2014/3/11
Y1 - 2014/3/11
N2 - 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.
AB - 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.
KW - MSC-91A12
U2 - 10.1016/j.dam.2012.08.002
DO - 10.1016/j.dam.2012.08.002
M3 - Article
SN - 0166-218X
VL - 165
SP - 175
EP - 184
JO - Discrete applied mathematics
JF - Discrete applied mathematics
ER -