Improved taxation rate for bin packing games

Walter Kern, X. Qui

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageUndefined
Title of host publicationFirst International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011
EditorsA. Marchetti-Spaccamela, M. Segal
Place of PublicationBerlin
PublisherSpringer
Pages175-180
Number of pages6
ISBN (Print)978-3-642-19753-6
DOIs
Publication statusPublished - 2011
EventFirst International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011 - Rome, Italy
Duration: 18 Apr 201120 Apr 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume6595
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceFirst International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems, TAPAS 2011
Period18/04/1120/04/11
Other18-20 April 2011

Keywords

  • METIS-279150
  • EWI-20098
  • IR-76832

Cite this