Anomalous behavior in bin packing algorithms |
| |
Affiliation: | Department of Information and Computer Science, University of California, Irvine, CA 92717, USA |
| |
Abstract: | In the classical bin packing problem one is given a list of items and asked to pack them into the fewest possible unit-sized bins. Given two lists, L1 and L2, where L2 is derived from L1 by deleting some elements of L1 and/or reducing the size of some elements of L1, one might hope that an approximation algorithm would use no more bins to pack L2 than it uses to pack L1. Johnson and Graham have given examples showing that First-Fit and First-Fit Decreasing can actually use more bins to pack L2 than L1. Graham has also studied this type of behavior among multiprocessor scheduling algorithms. In the present paper we extend this study of anomalous behavior to a broad class of approximation algorithms for bin packing. To do this we introduce a technique which allows one to characterize the monotonic/anomalous behavior of any algorithm in a large, natural class. We then derive upper and lower bounds on the anomalous behavior of the algorithms which are anomalous and provide conditions under which a normally nonmonotonic algorithm becomes monotonic. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|