| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 437632 | Theoretical Computer Science | 2010 | 9 Pages |
Abstract
It is well known that the two simple algorithms for the classic bin packing problem, and both have an approximation ratio of 2. However, seems to be a more reasonable algorithm, since it never opens a new bin if an existing bin can still be used.Using resource augmented analysis, where the output of an approximation algorithm, which can use bins of size b>1, is compared to an optimal packing into bins of size 1, we give a complete analysis of the asymptotic approximation ratio of and of , and use it to show that is strictly better than for any 1
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
