IMADA - Department of Mathematics and Computer Science |

**The Relative Worst Order Ratio for On-Line Algorithms***Joan Boyar and Lene M. Favrholdt*- Transactions on Algorithms, to appear
We define a new measure for the quality of on-line algorithms,
the Two variants of the bin packing problem are considered: the Classical Bin Packing problem, where the goal is to fit all items in as few bins as possible, and the Dual Bin Packing problem, which is the problem of maximizing the number of items packed in a fixed number of bins. Several known algorithms are compared using this new measure, and a new, simple variant of First-Fit is proposed for Dual Bin Packing. Many of our results are consistent with those previously obtained with the competitive ratio or the competitive ratio on accommodating sequences, but new separations and easier proofs are found.
The publication is available at portal.acm.org (subscription may be required). |

IMADA HOME | SDU HOME | Previous page Last modified: 2017-06-10 by Lene Monrad Favrholdt <lenem@imada.sdu.dk> |