Donald Bren School of Information and Computer Sciences

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.