Best-fit bin packing
Best-fit is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a packing - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem. The best-fit algorithm uses the following heuristic:
- It keeps a list of open bins, which is initially empty.
- When an item arrives, it finds the bin with the maximum load into which the item can fit, if any. The load of a bin is defined as the sum of sizes of existing items in the bin before placing the new item.
- If such a bin is found, the new item is placed inside it.
- Otherwise, a new bin is opened and the coming item is placed inside it.
Approximation ratio
Denote by BF(L) the number of bins used by Best-Fit, and by OPT(L) the optimal number of bins possible for the list L. The analysis of BF(L) was done in several steps.
- The first upper bound of [math]\displaystyle{ BF(L) \leq 1.7\mathrm{OPT}+3 }[/math] was proven by Ullman[1] in 1971.
- An improved upper bound [math]\displaystyle{ BF(L) \leq 1.7\mathrm{OPT}+2 }[/math] was proved by Garey, Graham and Ullman,[2] Johnson and Demers.[3]
- Afterward, it was improved by Garey, Graham, Johnson, Ullman, Yao and Chi-Chih[4] to [math]\displaystyle{ BF(L) \leq \lceil 1.7\mathrm{OPT}\rceil }[/math].
- Finally this bound was improved to [math]\displaystyle{ FF(L) \leq \lfloor 1.7\mathrm{OPT}\rfloor }[/math] by Dósa and Sgall.[5] They also present an example input list [math]\displaystyle{ L }[/math], for that [math]\displaystyle{ BF(L) }[/math] matches this bound.
Worst-fit
Worst-Fit is a "dual" algorithm to best-fit: it tries to put the next item in the bin with minimum load.
This algorithm can behave as badly as Next-Fit, and will do so on the worst-case list for that [math]\displaystyle{ NF(L) = 2 \cdot \mathrm{OPT}(L) -2 }[/math].[6] Furthermore, it holds that [math]\displaystyle{ R_{WF}^{\infty}(\text{size}\leq \alpha) = R_{NF}^{\infty}(\text{size}\leq \alpha) }[/math].
Since Worst-Fit is an AnyFit-algorithm, there exists an AnyFit-algorithm such that [math]\displaystyle{ R_{AF}^{\infty}(\alpha) = R_{NF}^{\infty}(\alpha) }[/math].[6]
References
- ↑ Ullman, J. D. (1971). "The performance of a memory allocation algorithm". Technical Report 100 Princeton Univ..
- ↑ Garey, M. R; Graham, R. L; Ullman, J. D. (1972). "Worst-case analysis of memory allocation algorithms" (in EN). Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. pp. 143–150. doi:10.1145/800152.804907.
- ↑ David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SICOMP, Volume 3, Issue 4. 1974.
- ↑ Garey, M. R; Graham, R. L; Johnson, D. S; Yao, Andrew Chi-Chih (1976). "Resource constrained scheduling as generalized bin packing" (in en). Journal of Combinatorial Theory, Series A 21 (3): 257–298. doi:10.1016/0097-3165(76)90001-7. ISSN 0097-3165.
- ↑ György, Dósa; Sgall, Jirí (2014). "Optimal Analysis of Best Fit Bin Packing". Automata, Languages, and Programming. Lecture Notes in Computer Science. 8572. pp. 429–441. doi:10.1007/978-3-662-43948-7_36. ISBN 978-3-662-43947-0.
- ↑ 6.0 6.1 Johnson, David S (1973). "Near-optimal bin packing algorithms". Massachusetts Institute of Technology. https://dspace.mit.edu/bitstream/handle/1721.1/57819/17595570-MIT.pdf?sequence=2.
 |  |
