Best-fit bin packing

Last updated December 19, 2023

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 $BF(L)\leq 1.7\mathrm {OPT} +3$ was proven by Ullman^[1] in 1971.
An improved upper bound $BF(L)\leq 1.7\mathrm {OPT} +2$ 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 $BF(L)\leq \lceil 1.7\mathrm {OPT} \rceil$ .
Finally this bound was improved to $FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor$ by Dósa and Sgall.^[5] They also present an example input list $L$ , for that $BF(L)$ 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 $NF(L)=2\cdot \mathrm {OPT} (L)-2$ .^[6] Furthermore, it holds that $R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )$ .

Since Worst-Fit is an AnyFit-algorithm, there exists an AnyFit-algorithm such that $R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )$ .^[6]

Related Research Articles

The knapsack problem is the following problem in combinatorial optimization:

The Pareto distribution, named after the Italian civil engineer, economist, and sociologist Vilfredo Pareto, is a power-law probability distribution that is used in description of social, quality control, scientific, geophysical, actuarial, and many other types of observable phenomena; the principle originally applied to describing the distribution of wealth in a society, fitting the trend that a large portion of wealth is held by a small fraction of the population. The Pareto principle or "80-20 rule" stating that 80% of outcomes are due to 20% of causes was named in honour of Pareto, but the concepts are distinct, and only Pareto distributions with shape value of log₄5 ≈ 1.16 precisely reflect it. Empirical observation has shown that this 80-20 distribution fits a wide range of cases, including natural phenomena and human activities.

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, and technology mapping in FPGA semiconductor chip design.

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.

In mathematics, the question of whether the Fourier series of a periodic function converges to a given function is researched by a field known as classical harmonic analysis, a branch of pure mathematics. Convergence is not necessarily given in the general case, and certain criteria must be met for convergence to occur.

In information theory, the Rényi entropy is a quantity that generalizes various notions of entropy, including Hartley entropy, Shannon entropy, collision entropy, and min-entropy. The Rényi entropy is named after Alfréd Rényi, who looked for the most general way to quantify information while preserving additivity for independent events. In the context of fractal dimension estimation, the Rényi entropy forms the basis of the concept of generalized dimensions.

In computer science, particularly the study of approximation algorithms, an L-reduction is a transformation of optimization problems which linearly preserves approximability features; it is one type of approximation-preserving reduction. L-reductions in studies of approximability of optimization problems play a similar role to that of polynomial reductions in the studies of computational complexity of decision problems.

In probability theory and statistics, the beta-binomial distribution is a family of discrete probability distributions on a finite support of non-negative integers arising when the probability of success in each of a fixed or known number of Bernoulli trials is either unknown or random. The beta-binomial distribution is the binomial distribution in which the probability of success at each of n trials is not fixed but randomly drawn from a beta distribution. It is frequently used in Bayesian statistics, empirical Bayes methods and classical statistics to capture overdispersion in binomial type distributed data.

Subgradient methods are iterative methods for solving convex minimization problems. Originally developed by Naum Z. Shor and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function. When the objective function is differentiable, sub-gradient methods for unconstrained problems use the same search direction as the method of steepest descent.

The strip packing problem is a 2-dimensional geometric minimization problem. Given a set of axis-aligned rectangles and a strip of bounded width and infinite height, determine an overlapping-free packing of the rectangles into the strip minimizing its height. This problem is a cutting and packing problem and is classified as an Open Dimension Problem according to Wäscher et al.

In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the identical-machines scheduling problem. The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers, whose sum is k*T.

In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used.

The multifit algorithm is an algorithm for multiway number partitioning, originally developed for the problem of identical-machines scheduling. It was developed by Coffman, Garey and Johnson. Its novelty comes from the fact that it uses an algorithm for another famous problem - the bin packing problem - as a subroutine.

Next-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 next-fit algorithm uses the following heuristic:

First-fit (FF) 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 first-fit algorithm uses the following heuristic:

Harmonic bin-packing is a family of online algorithms for bin packing. The input to such an algorithm is a list of items of different sizes. The 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.

First-fit-decreasing (FFD) is an 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, so we use an approximately-optimal heuristic.

Next-fit-decreasing (NFD) is an 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 NFD algorithm uses the following heuristic:

High-multiplicity bin packing is a special case of the bin packing problem, in which the number of different item-sizes is small, while the number of items with each size is large. While the general bin-packing problem is NP-hard, the high-multiplicity setting can be solved in polynomial time, assuming that the number of different sizes is a fixed constant.

The Karmarkar–Karp (KK) bin packing algorithms are several related approximation algorithm for the bin packing problem. The bin packing problem is a problem of packing items of different sizes into bins of identical capacity, such that the total number of bins is as small as possible. Finding the optimal solution is computationally hard. Karmarkar and Karp devised an algorithm that runs in polynomial time and finds a solution with at most $bins, where OPT is the number of bins in the optimal solution. They also devised several other algorithms with slightly different approximation guarantees and run-time bounds.$

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". Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. pp. 143–150. doi:10.1145/800152.804907. S2CID 26654056.
↑ 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". 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. Vol. 8572. pp. 429–441. doi:10.1007/978-3-662-43948-7_36. ISBN 978-3-662-43947-0.
1 2 Johnson, David S (1973). "Near-optimal bin packing algorithms" (PDF). Massachusetts Institute of Technology.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Ullman71-1] Ullman, J. D. (1971). "The performance of a memory allocation algorithm". Technical Report 100 Princeton Univ.

[GareyGU72-2] Garey, M. R; Graham, R. L; Ullman, J. D. (1972). "Worst-case analysis of memory allocation algorithms". Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. pp. 143–150. doi:10.1145/800152.804907. S2CID 26654056.

[3] 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.

[GareyGJY-4] Garey, M. R; Graham, R. L; Johnson, D. S; Yao, Andrew Chi-Chih (1976). "Resource constrained scheduling as generalized bin packing". Journal of Combinatorial Theory, Series A. 21 (3): 257–298. doi: 10.1016/0097-3165(76)90001-7 . ISSN 0097-3165.

[DósaSgall14-5] György, Dósa; Sgall, Jirí (2014). "Optimal Analysis of Best Fit Bin Packing". Automata, Languages, and Programming. Lecture Notes in Computer Science. Vol. 8572. pp. 429–441. doi:10.1007/978-3-662-43948-7_36. ISBN 978-3-662-43947-0.

[johnson732-6] 1 2 Johnson, David S (1973). "Near-optimal bin packing algorithms" (PDF). Massachusetts Institute of Technology.

[1]

[2]

[3]

[4]

[5]

[6]

Best-fit bin packing

Contents

Approximation ratio

Worst-fit

Related Research Articles

References