Algorithms for the relaxed online bin-packing model

The typical online bin-packing problem requires the fitting of a sequence o f rationals in (0, 1] into a minimum number of bins of unit capacity, by pa cking the ith input element without any knowledge of the sizes or the numbe r 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 for malized; this model allows a constant number of elements to move from one b in 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 descr ibed. The first presents linear time and space complexities with a 1.5 appr oximation ratio and moves, at most once, only small elements; the second, i nstead, is an O (n log n) time and linear space algorithm with a 1.33... ap proximation 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 alg orithm moves no more than three elements, while the second moves as many as seven elements. Please note that the number of movements performed is expl icitly 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. Mor eover, our algorithms are more online than any other linear space online bi n-packing algorithm because, unlike the algorithms already known, they allo w the return of a ( possibly relevant) fraction of bins before the work is carried out.