Improved taxation rate for bin packing games

Kern, Walter and Qiu, Xian (2011) Improved taxation rate for bin packing games. In: First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011, 18-20 April 2011, Rome, Italy.

PDF
Restricted to UT campus only: Request a copy
270Kb

Abstract:	A cooperative bin packing game is a $N$ -person game, where the player set $N$ consists of $k$ bins of capacity 1 each and $n$ items of sizes $a_1,\dots,a_n$ . 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 present an alternative proof for the non-emptiness of the 1/3-core for all bin packing games and show how to improve this bound $\epsilon = 1/3$ (slightly). We conjecture that the true best possible value is $\epsilon= 1/7$ .
Item Type:	Conference or Workshop Item
Copyright:	© 2011 Springer
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/76832
Official URL:	http://dx.doi.org/10.1007/978-3-642-19754-3_18
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 279150