Improved taxation rate for bin packing games

Walter Kern; X. Qui

doi:10.1007/978-3-642-19754-3_18

Improved taxation rate for bin packing games

Walter Kern, X. Qui

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

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$.

Original language	Undefined
Title of host publication	First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011
Editors	A. Marchetti-Spaccamela, M. Segal
Place of Publication	Berlin
Publisher	Springer
Pages	175-180
Number of pages	6
ISBN (Print)	978-3-642-19753-6
DOIs	https://doi.org/10.1007/978-3-642-19754-3_18
Publication status	Published - 2011
Event	First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011 - Rome, Italy Duration: 18 Apr 2011 → 20 Apr 2011

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	6595
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011
Period	18/04/11 → 20/04/11
Other	18-20 April 2011

Keywords

METIS-279150
EWI-20098
IR-76832

Access to Document

10.1007/978-3-642-19754-3_18

http://eprints.eemcs.utwente.nl/secure2/20098/01/binpacking.pdf

Cite this

@inproceedings{3a6028793b8f449e9abea5c46a52f7c4,

title = "Improved taxation rate for bin packing games",

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$.",

keywords = "METIS-279150, EWI-20098, IR-76832",

author = "Walter Kern and X. Qui",

note = "eemcs-eprint-20098 ; null ; Conference date: 18-04-2011 Through 20-04-2011",

year = "2011",

doi = "10.1007/978-3-642-19754-3_18",

language = "Undefined",

isbn = "978-3-642-19753-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "175--180",

editor = "A. Marchetti-Spaccamela and M. Segal",

booktitle = "First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011",

}

Kern, W & Qui, X 2011, Improved taxation rate for bin packing games. in A Marchetti-Spaccamela & M Segal (eds), First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011. Lecture Notes in Computer Science, vol. 6595, Springer, Berlin, pp. 175-180, First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011, 18/04/11. https://doi.org/10.1007/978-3-642-19754-3_18

Improved taxation rate for bin packing games. / Kern, Walter; Qui, X.

First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011. ed. / A. Marchetti-Spaccamela; M. Segal. Berlin : Springer, 2011. p. 175-180 (Lecture Notes in Computer Science; Vol. 6595).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Improved taxation rate for bin packing games

AU - Kern, Walter

AU - Qui, X.

N1 - eemcs-eprint-20098

PY - 2011

Y1 - 2011

N2 - 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$.

AB - 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$.

KW - METIS-279150

KW - EWI-20098

KW - IR-76832

U2 - 10.1007/978-3-642-19754-3_18

DO - 10.1007/978-3-642-19754-3_18

M3 - Conference contribution

SN - 978-3-642-19753-6

T3 - Lecture Notes in Computer Science

SP - 175

EP - 180

BT - First International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011

A2 - Marchetti-Spaccamela, A.

A2 - Segal, M.

PB - Springer

CY - Berlin

Y2 - 18 April 2011 through 20 April 2011

ER -