Online bin packing with resource augmentation

Online bin packing with resource augmentation

0.00 Avg rating0 Votes
Article ID: iaor20083869
Country: Netherlands
Volume: 4
Issue: 3/4
Start Page Number: 322
End Page Number: 333
Publication Date: Dec 2007
Journal: Discrete Optimization
Authors: ,
Keywords: bin packing
Abstract:

In competitive analysis, we usually do not put any restrictions on the computational complexity of online algorithms, although efficient algorithms are preferred. Thus, if such an algorithm were given the entire input in advance, it could give an optimal solution (in exponential time). Instead of giving the algorithm more knowledge about the input, in this paper we consider the effects of giving an online bin packing algorithm larger bins than the offline algorithm it is compared to. We give new algorithms for this problem that combine items in bins in an unusual way, and give bounds on their performance which improve upon the best possible bounded space algorithm. We also give general lower bounds for this problem which are nearly matching for bin sizes b≥2.

Reviews

Required fields are marked *. Your email address will not be published.