AbstractThe classical on-line bin-packing problem, unlike typical on-line problems, does not admit any reorganization of its data, i.e. no element can be moved from the bin it was first inserted.
In this paper we introduce a new model for this problem, in which an element can possibly be moved in correspondence of the arrival of another element, but the number of movements performed is explicitly considered in the complexity analysis.
In the framework of this paradigm, we introduce a new class of O(n log n) - time and O(n) - space algorithms, HARMONIC_REL(M) (where M > 2 is an integer), that, for each prefix of the input list, obtain a new bin assignment performing a limited reorganization of the previous solution, making, at most, cn element movements (c = 2 for M = 3). All of the algorithms in this class present an 1.5 asymptotic approximation ratio (and an 1.5 OPT + (M - 1) absolute ratio), that goes beyond the theoretical 1.536... lower bound for on-line bin-packing in the restricted model.
Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]; G.2 [Discrete Mathematics]
Additional Key Words and Phrases: complexity, approximation algorithms, on-line algorithms, bin packing
Selected references
- E. G. Coffman, Jr., Kimming So, Micha Hofri, and A. C. Yao. A stochastic model of bin-packing. Information and Control, 44(2):105-115, February 1980.
- J. Csirik and D. S. Johnson. Bounded space on-line bin packing: Best is better than first. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 309-319, San Francisco, California, 28-30 January 1991.
- David S. Johnson. Fast algorithms for bin packing. Journal of Computer and System Sciences, 8(3):272-314, June 1974.
- C. C. Lee and D. T. Lee. A simple on-line bin-packing algorithm. Journal of the ACM, 32(3):562-572, July 1985.
- Frank M. Liang. A lower bound for on-line bin packing. Information Processing Letters, 10(2):76-79, 18 March 1980.
- Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11(2):208-230, June 1990.
- Prakash Ramanan. Average-case analysis of Smart Next Fit algorithm. Information Processing Letters, 31(5):221-225, 12 June 1989.
- Prakash Ramanan, Donna J. Brown, C. C. Lee, and D. T. Lee. On-line bin packing in linear time. Journal of Algorithms, 10(3):305-326, September 1989.
- Prakash V. Ramanan and Kazuhiro Tsuga. Average-case analysis of the modified harmonic algorithm. Algorithmica, 4:519-533, 1989.