The typical online bin-packing problem requires the fitting of a sequence of rationals in (0, 1] into a minimum number of bins of unit capacity, by packing the ith input element without any knowledge of the sizes or the number of input elements that follow. Moreover, unlike typical online problems, this one issue does not admit any data reorganization, i.e., no element can be moved from one bin to another. In this paper, rst of all, the Relaxed online bin-packing model will be formalized; this model allows a constant number of elements to move from one bin to another, as a consequence of the arrival of a new input element. Then, in the context of this new model, two online algorithms will be described. The first presents linear time and space complexities with a 1.5 approximation ratio and moves, at most once, only small elements; the second, instead, is an O (n log n) time and linear space algorithm with a 1.33... approximation ratio and moves each element a constant number of times. In the worst case, as a result of the arrival of a new input element, the rst algorithm moves no more than three elements, while the second moves as many as seven elements. Please note that the number of movements performed is explicitly considered in the complexity analysis. Both algorithms are below the theoretical 1. 536... lower bound, effective for the online bin-packing algorithms without the movement of elements. Moreover, our algorithms are more online than any other linear space online bin-packing algorithm because, unlike the algorithms already known, they allow the return of a ( possibly relevant) fraction of bins before the work is carried out.

Gambosi, G., Postiglione, A., & Talamo, M. (2000). Algorithms for the relaxed online bin-packing model. SIAM JOURNAL ON COMPUTING, 30(5), 1532-1551 [10.1137/S0097539799180408].

Algorithms for the relaxed online bin-packing model

GAMBOSI, GIORGIO;TALAMO, MAURIZIO
2000

Abstract

The typical online bin-packing problem requires the fitting of a sequence of rationals in (0, 1] into a minimum number of bins of unit capacity, by packing the ith input element without any knowledge of the sizes or the number of input elements that follow. Moreover, unlike typical online problems, this one issue does not admit any data reorganization, i.e., no element can be moved from one bin to another. In this paper, rst of all, the Relaxed online bin-packing model will be formalized; this model allows a constant number of elements to move from one bin to another, as a consequence of the arrival of a new input element. Then, in the context of this new model, two online algorithms will be described. The first presents linear time and space complexities with a 1.5 approximation ratio and moves, at most once, only small elements; the second, instead, is an O (n log n) time and linear space algorithm with a 1.33... approximation ratio and moves each element a constant number of times. In the worst case, as a result of the arrival of a new input element, the rst algorithm moves no more than three elements, while the second moves as many as seven elements. Please note that the number of movements performed is explicitly considered in the complexity analysis. Both algorithms are below the theoretical 1. 536... lower bound, effective for the online bin-packing algorithms without the movement of elements. Moreover, our algorithms are more online than any other linear space online bin-packing algorithm because, unlike the algorithms already known, they allow the return of a ( possibly relevant) fraction of bins before the work is carried out.
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore INF/01 - Informatica
English
Approximation algorithms; Bin packing; Complexity; Online algorithms
Gambosi, G., Postiglione, A., & Talamo, M. (2000). Algorithms for the relaxed online bin-packing model. SIAM JOURNAL ON COMPUTING, 30(5), 1532-1551 [10.1137/S0097539799180408].
Gambosi, G; Postiglione, A; Talamo, M
Articolo su rivista
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/2108/41897
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 30
social impact