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-01-01
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.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.
