Comparing online algorithms for bin packing problems

Description:

Leah Epstein, Lene M. Favrholdt, and Jens S. Kohrt. Comparing online algorithms for bin packing problems. Technical Report IMADA-PP-2009-01, Department of Mathematics and Computer Science, University of Southern Denmark, Odense, 2009.

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.

Availability:

Available as pdf (170 KB).
Also available at the DMF Preprint Server.

Related Papers:

• Comparing online algorithms for bin packing problems (Journal Paper)
• Comparing online algorithms for bin packing problems (Submission)