✦ LIBER ✦

Average-case analysis of the bin-packing problem with general cost structures

✍ Scribed by Julien Bramel; WanSoo T. Rhee; David Simchi-Levi

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 100 KB
Volume: 44
Category: Article
ISSN: 0894-069X
DOI: 10.1002/(sici)1520-6750(199710)44:7<673::aid-nav5>3.0.co;2-9

No coin nor oath required. For personal study only.

✦ Synopsis

We consider a version of the famous bin-packing problem where the cost of a bin is a concave function of the number of items in the bin. We analyze the problem from an average-case point of view and develop techniques to determine the asymptotic optimal solution value for a variety of functions. We also describe heuristic techniques that are asymptotically optimal.