Approximate core allocations and integrality gap for the bin packing game

Walter Kern, X. Qui

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

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 $a_1,...,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 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.
Original languageUndefined
Pages (from-to)26-35
Number of pages10
JournalTheoretical computer science
Volume627
DOIs
Publication statusPublished - 9 May 2016

Keywords

  • EWI-27505
  • Bin packing
  • Integrality gap
  • METIS-320913
  • Core
  • Subset sum
  • IR-103052
  • Cooperative game

Cite this