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

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/4757189
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact