|
 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.d
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
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.
|
| |
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.
|
| |
3
|
|
| |
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.
|
| |
5
|
JOHNSON, D.S.Near optimal bin packing algorithms. Ph.D. dissertation, MIT, Cambridge, Mass., June 1973.
|
| |
6
|
JOHNSON, D.S.Fast algorithms for bin packing. J. Comput. Syst. Sci. 8 (1974), 272-314.
|
| |
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.
|
| |
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.
|
| |
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.
|
| |
10
|
LEE, C.C., AND LEE, D.T.Robust on-line bin packing algorithms. Submitted for publication.
|
| |
11
|
LIANG, F. M. A lower bound for on-line bin packing. Inf. Proc. Lett. 10 (1980), 76-79.
|
 |
12
|
|
CITED BY 24
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Y.-P. Pang , T. J. Mullins , B. A. Swartz , J. S. McAllister , B. E. Smith , C. J. Archer , R. G. Musselman , A. E. Peters , B. P. Wallenfelt , K. W. Pinnow, EUDOC on the IBM Blue Gene/L system: accelerating the transfer of drug discoveries from laboratory to patient, IBM Journal of Research and Development, v.52 n.1, p.69-81, January 2008
|
|
|
|
|
|
|
|
|
|
|
|
Nikhil Bansal , Xin Han , Kazuo Iwama , Maxim Sviridenko , Guochuan Zhang, Harmonic algorithm for 3-dimensional strip packing problem, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1197-1206, January 07-09, 2007, New Orleans, Louisiana
|
|
|
|
|
|
|
|
|
|
REVIEW
"Michael R. Garey : Reviewer"
In the classical one-dimensional bin packing problem, one is given a list
a1, a2, . . . , an of items, each with
a size between 0 and 1, and is asked to pack these items int
more...
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2