Article ID Journal Published Year Pages File Type
435325 Theoretical Computer Science 2016 10 Pages PDF
Abstract

A cooperative (uniform) bin packing game is an N-person game, where the player set consists of k bins of capacity 1 each and n   items of sizes a1,…,ana1,…,an. The value of a coalition of players is defined to be the maximum total size of items in the coalition that can be packed into the bins of the coalition. We aim at finding a multiplicative ϵ-core allocation with ϵ as small as possible, thus approximating the core as closely as possible. Our main result shows that the 1/4-core is nonempty for all instances of the uniform bin packing game.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,