APPROXIMATE CORE ALLOCATION FOR BINPACKING GAMES

A binpacking game is a cooperative N-person game, where the set of pla yers consists of k bins of size 1 and n items of sizes a(1),...,a(n). The value of a coalition of bins and items is the maximum total size o f items in the coalition that can be packed into the bins of the coali tion. Our main result asserts that for every epsilon > 0, there exist epsilon-approximate core allocations provided k is large enough. Moreo ver, for every fixed delta > 0, the smallest epsilon for which the eps ilon-approximate core of a given binpacking game is nonempty can be co mputed in polynomial time with error at most delta, provided k is suff iciently large. We furthermore derive more specialized results for som e subclasses of binpacking games.