The 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.
On line maintainance of a solution for bin-packing
Alberto Postiglione
;
1997-01-01
Abstract
The 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
