Next-fit bin packing

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:

• It keeps a current bin, which is initially empty.
• When an item arrives, it checks whether the item fits into the current bin.
  • If it fits, it is placed inside it.
  • Otherwise, the current bin is closed, a new bin is opened and the coming item is placed inside this new bin.

Next-Fit is a bounded space algorithm - it requires only one partially-filled bin to be open at any time. The algorithm was studied by David S. Johnson in his doctoral thesis ^[1] in 1973.

Run time

The running time of NextFit can be bounded by ${\displaystyle {\mathcal {O}}(n)}$, where ${\displaystyle n}$ is the number of items in the list. ^[2]

Approximation ratio

Denote by NF(L) the number of bins used by NextFit, and by OPT(L) the optimal number of bins possible for the list L.

Upper bound

Then, for each list ${\displaystyle L}$, ${\displaystyle NF(L)\leqslant 2\cdot \mathrm {OPT} (L)-1}$. For the sake of convenience, assume that each bin has a maximum capacity of ${\displaystyle 1}$. The intuition behind the proof is the following. If ${\displaystyle K^{*}}$ is the optimal number of bins, then ${\displaystyle K^{*}\geqslant \left\lceil \sum _{i\in I}s(i)\right\rceil }$. This follows from the fact that otherwise, at least one bin in an optimal solution would exceed the capacity, and that ${\displaystyle K^{*}}$ is an integer.

Due to the structure of the algorithm, the total size of two consecutive bins (except for the last one) exceeds ${\displaystyle 1}$. This means that if ${\displaystyle K}$ is the number of bins produced by the algorithm, then ${\displaystyle \left\lfloor {\frac {K}{2}}\right\rfloor <\sum _{i\in I}s(i)}$.

Combining both inequalities, we get ${\displaystyle {\frac {K-1}{2}}\leqslant \left\lfloor {\frac {K}{2}}\right\rfloor \leqslant \left\lceil \sum _{i\in I}s(i)\right\rceil -1\leqslant K^{*}-1}$, thus ${\displaystyle K\leqslant 2K^{*}-1}$.

Lower bound

For each ${\displaystyle N\in \mathbb {N} }$, there exists a list ${\displaystyle L}$ such that ${\displaystyle \mathrm {OPT} (L)=N}$ and ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$.

The family of lists for which it holds that ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$ is given by ${\displaystyle L:=\left({\frac {1}{2}},{\frac {1}{2(N-1)}},{\frac {1}{2}},{\frac {1}{2(N-1)}},\dots ,{\frac {1}{2}},{\frac {1}{2(N-1)}}\right)}$ with ${\displaystyle |L|=4(N-1)}$. The optimal solution for this list has ${\displaystyle N-1}$ bins containing two items with size ${\displaystyle 1/2}$ and one bin with ${\displaystyle 2(N-1)}$ items with size ${\displaystyle 1/2(N-1)}$ (i.e., ${\displaystyle N}$ bins total), while the solution generated by NF has ${\displaystyle 2(N-1)}$ bins with one item of size ${\displaystyle 1/2}$ and one item with size ${\displaystyle 1/(2(N-1))}$.

Bounded item size

If the maximum size of an item is ${\displaystyle \alpha }$, then the asymptotic approximation ratio ratio ${\displaystyle R_{NF}^{\infty }}$ satisfies:

• ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2}$ for all ${\displaystyle \alpha \geq 1/2}$;
• ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )}$ for all ${\displaystyle \alpha \leq 1/2}$.

Other properties

Next-Fit packs a list and its inverse into the same number of bins. ^[3]

Next-k-Fit (NkF)

Next-k-Fit is a variant of Next-Fit, but instead of keeping only one bin open, the algorithm keeps the last ${\displaystyle k}$ bins open and chooses the first bin in which the item fits.

For ${\displaystyle k\geq 2}$, NkF delivers results that are improved compared to the results of NF, however, increasing ${\displaystyle k}$ to constant values larger than ${\displaystyle 2}$ improves the algorithm no further in its worst-case behavior. If algorithm ${\displaystyle A}$ is an AlmostAnyFit-algorithm and ${\displaystyle m=\lfloor 1/\alpha \rfloor \geq 2}$ then ${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/m}$. ^[1]

See also

• Next-fit-decreasing (NFD) is the offline variant of Next-Fit: it accepts all input items, orders them by descending size, and calls Next-Fit. Its asymptotic approximation ratio is much better: less than 1.7, instead of 2.

References

1. Johnson, David S (1973). "Near-optimal bin packing algorithms" (PDF). Massachusetts Institute of Technology.
2. Suri, Subhash. "Bin Packing". UCSB Computer Science. Retrieved 7 October 2021.
3. Fisher, David C. (1988-12-01). "Next-fit packs a list and its reverse into the same number of bins" . Operations Research Letters. 7 (6): 291–293. doi:10.1016/0167-6377(88)90060-0. ISSN   0167-6377.