C. C. Lee
Abstract
The one-dimensional on-line bin-packing problem is considered, A simple O(1)-space and O(n)-time algorithm, called HARMONICM, is presented. It is shown that this algorithm can achieve a worst-case performance ratio of less than 1.692, which is better than that of the O(n)-space and O(n log n)-time algorithm FIRST FIT. Also shown is that 1.691 … is a lower bound for all 0(1)-space on-line bin-packing algorithms. Finally a revised version of HARMONICM , an O(n)-space and O(n)- time algorithm, is presented and is shown to have a worst-case performance ratio of less than 1.636.
- 1 BROWN, D.J.A lower bound for on-line one-dimensional bin packing algorithms. Tech. Rep. No. R-864, Coordinated Sci. Lab., Univ. of Illinois, Urbana, I11., 1979.Google Scholar
- 2 COFFMAN, E.G., jR., GAREY, M.R., AND JOHNSON, D.S. Approximation algorithms for binpackingmAn updated survey. Bell Laboratories, Murray Hill, N.J., Oct. I983.Google Scholar
- 3 GAREY, M.R., AND JOHNSON, D.S.Computers and Intractability: A Guide to the Theory of NP- completeness. W. H. Freeman & Co., San Francisco, Calif., 1979. Google Scholar
- 4 GAREY, M. R., AND JOHNSON, D. S. Approximation algorithms for bin packing problems: A survey. In Analysis and Design of Algorithms in Combinatorial Optimization, G. Ausiello and M. Lucertini, Eds. Springer-Verlag, New York, 1981.Google Scholar
- 5 JOHNSON, D.S.Near optimal bin packing algorithms. Ph.D. dissertation, MIT, Cambridge, Mass., June 1973.Google Scholar
- 6 JOHNSON, D.S.Fast algorithms for bin packing. J. Comput. Syst. Sci. 8 (1974), 272-314.Google Scholar
- 7 JOHNSON, D.S., DEMERS, A., ULLMAN, J.D., GAREY, M.R., AND GRAHAM, R.U Worst-case performance bounds for simple one-dimensional bin packing algorithms. SIAM J. Comput. 3 (1974), 299-325.Google Scholar
- 8 KARP, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computations, R.E. Miller and J.M. Thatcher, Eds. Plenum Press, New York, 1972, pp. 85-103.Google Scholar
- 9 LEE, C.C., AND LEE, D.T. A new algorithm for on-line bin packing. Tech. Rep. No. 83-03-FC- 02, Dept. of Electrical Engineering and Computer Science, Northwestern Univ., Evanston, I11., Nov. 1983.Google Scholar
- 10 LEE, C.C., AND LEE, D.T.Robust on-line bin packing algorithms. Submitted for publication.Google Scholar
- 11 LIANG, F. M. A lower bound for on-line bin packing. Inf. Proc. Lett. 10 (1980), 76-79.Google Scholar
- 12 YAO, A.C. New algorithms for bin packing. J. ACM. 27 (1980), 207-227. Google Scholar
Index Terms
- A simple on-line bin-packing algorithm
Recommendations
An on-line algorithm for multidimensional bin packing
In this paper we present an on-line algorithm for the d-dimensional bin packing problem. We use the idea of rounding up the size of an item to a size that can be packed efficiently. Although our algorithm is not a generalization of the 1-dimensional ...
On-line algorithms for 2-space bounded 2-dimensional bin packing
In 2-space bounded model of on-line bin packing, there are 2 active bins, and each item can be packed only into one of the active bins. If it is impossible to pack an item into any active bin, we close one of the current active bins and open a new ...
Strip Packing vs. Bin Packing
AAIM '07: Proceedings of the 3rd international conference on Algorithmic Aspects in Information and ManagementIn this paper we establish a general algorithmic framework between bin packing and strip packing, with which we achieve the same asymptotic bounds by applying bin packing algorithms to strip packing. More precisely we obtain the following results: (1) ...
Reviews
Michael R. Garey
In the classical one-dimensional bin packing problem, one is given a list a 1, a 2, . . . , a n of items, each with a size between 0 and 1, and is asked to pack these items into as few bins as possible so that no bin contains items whose sizes sum to more than 1. This NP-hard problem arises in a wide variety of applications and has been studied extensively from the point of view of proving theoretical performance bounds for fast approximation algorithms. This paper concentrates on on-line algorithms for such problems, i.e., algorithms that decide where to pack each item before seeing any of the items that appear later in the list. The main results are (1) a linear time, constant space algorithm that is guaranteed never to exceed the optimal number of bins by more than 69.2 percent, (2) a proof that no constant space algorithm can satisfy a significantly better performance bound than this, and (3) a linear time, linear space variant of the method that is guaranteed never to exceed the optimal number of bins by more than 63.6 percent. Recent (unpublished) results by the authors and P. Ramanan and D. J. Brown claim significant improvements over the performance bound in (3).
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments