Comparing online algorithms for bin packing problems

Comparing online algorithms for bin packing problems

0.00 Avg rating0 Votes
Article ID: iaor2012922
Volume: 15
Issue: 1
Start Page Number: 13
End Page Number: 21
Publication Date: Feb 2012
Journal: Journal of Scheduling
Authors: , ,
Keywords: analysis of algorithms, bin packing
Abstract:

The relative worst‐order ratio is a measure of the quality of online algorithms. In contrast to the competitive ratio, this measure compares two online algorithms directly instead of using an intermediate comparison with an optimal offline algorithm. In this paper, we apply the relative worst‐order ratio to online algorithms for several common variants of the bin packing problem. We mainly consider pairs of algorithms that are not distinguished by the competitive ratio and show that the relative worst‐order ratio prefers the intuitively better algorithm of each pair.

Reviews

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