Skip to main content
Open Access Publications from the University of California

On the monotonicity of certain bin packing algorithms


This paper examines the monotonicity of the approximation bin packing algorithms Worst-Fit (WF), Worst-Fit Decreasing (WFD), Best-Fit (BF), Best-Fit Decreasing (BFD), and Next-Fit-k (NF-k). Let X and Y be two sets of items such that the set X can be derived from the set Y by possibly deleting some members of Y or by reducing the size of some members of Y. If an algorithm never uses more bins to pack X than it uses to pack Y we say that algorithm is monotonic. It is shown that NF and NF-2 are monotonic. It was already known that First-Fit and First-Fit Decreasing were non-monotonic and we give examples which show BF, BFD, WF, and WFD also suffer from this anomaly. One may consider First-Fit as the limiting case of NF-k. We notice that NF-1 is monotonic while First-Fit is not, suggesting there exists some critical k for which NF-k' is monotonic, for k' k. We establish that this is indeed the case and determine that critical k. An upper bound on the non-monotonicity of selected algorithms is also provided.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View