In this paper, two new algorithms for on-line bin packing are given, under the assumption that each element can be moved for a constant number of times after its first assignment to some bin. The first algorithm presents linea time and space complexities with a 1.5 approximation ratio, while the second one is a O(n log n) time and linear space one with a 1.33... approximation ratio. Both algorithms present an approximation rate less than the 1.53 lower bound for on-line bin-packing without element movements.

New Algorithms for on-line bin-packing

Alberto Postiglione
;
1990

Abstract

In this paper, two new algorithms for on-line bin packing are given, under the assumption that each element can be moved for a constant number of times after its first assignment to some bin. The first algorithm presents linea time and space complexities with a 1.5 approximation ratio, while the second one is a O(n log n) time and linear space one with a 1.33... approximation ratio. Both algorithms present an approximation rate less than the 1.53 lower bound for on-line bin-packing without element movements.
9810203985
9810203993
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/4757184
 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