Name
Abstract | ||
|---|---|---|
The NP-hard problem of packing items from a given set into bins so as to maximize the number of bins used, subject to the constraint that each bin be filled to at least a given threshold, is considered. Approximation algorithms are presented that provide guarantees of 12, 23, and 34 the optimal number, at running time costs of O(n), O(nlogn), and O(nlog2n), respectively, and the average case behavior of these algorithms is explored via empirical tests on randomly generated sets of items. |
Year | DOI | Venue |
|---|---|---|
1984 | 10.1016/0196-6774(84)90004-X | Journal of Algorithms |
Keywords | Field | DocType |
bin packing problem | Discrete mathematics,Approximation algorithm,Combinatorics,Bin,APX,Mathematics,Bin packing problem | Journal |
Volume | Issue | ISSN |
5 | 4 | 0196-6774 |
Citations | PageRank | References |
82 | 8.32 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. F. Assmann | 1 | 87 | 17.07 |
| David S. Johnson | 2 | 1090 | 294.67 |
| Daniel J. Kleitman | 3 | 854 | 277.98 |
| Joseph Y. -T. Leung | 4 | 2403 | 400.82 |