Algorithms for the Relaxed Online Bin-Packing Model

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, t...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2000-01, Vol.30 (5), p.1532-1551
Main Authors: Gambosi, Giorgio, Postiglione, Alberto, Talamo, Maurizio
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Linear programming
Packing problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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, first 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 first 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.
ISSN:0097-5397
1095-7111
DOI:10.1137/S0097539799180408