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.