Joan Boyar
Abstract
We define a new measure for the quality of online algorithms, the relative worst order ratio, using ideas from the max/max ratio [Ben-David and Borodin 1994] and from the random order ratio [Kenyon 1996]. The new ratio is used to compare online algorithms directly by taking the ratio of their performances on their respective worst permutations of a worst-case sequence.
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.
- Azar, Y., Boyar, J., Epstein, L., Favrholdt, L. M., Larsen, K. S., and Nielsen, M. N. 2002. Fair versus unrestricted bin packing. Algorithmica 34, 2, 181--196.Google Scholar
Digital Library
- Ben-David, S., and Borodin, A. 1994. A new measure for the study of on-line algorithms. Algorithmica 11, 1, 73--91.Google ScholarDigital Library
- Boyar, J., Epstein, L., Favrholdt, L. M., Kohrt, J. S., Larsen, K. S., Pedersen, M. M., and Wøhlk, S. 2006. The maximum resource bin packing problem. Theor. Comput. Sci. 362, 127--139. Google ScholarDigital Library
- Boyar, J., Favrholdt, L. M., and Larsen, K. S. 2007. The relative worst order ratio applied to paging. J. Comput. Syst. Sci. 73, 818--843. Google ScholarDigital Library
- Boyar, J., Favrholdt, L. M., Larsen, K. S., and Nielsen, M. N. 2001a. The competitive ratio for on-line dual bin packing with restricted input sequences. Nordic J. Comput. 8, 4, 463--472. Google ScholarDigital Library
- Boyar, J., and Larsen, K. S. 1999. The seat reservation problem. Algorithmica 25, 403--417.Google ScholarCross Ref
- Boyar, J., Larsen, K. S., and Nielsen, M. N. 2001b. The accommodating function---A generalization of the competitive ratio. SIAM J. Comput. 31, 1, 233--258. Google ScholarDigital Library
- Boyar, J., and Medvedev, P. 2004. The relative worst order ratio applied to seat reservation. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 3111. Springer Verlag, Berlin. 90--101.Google Scholar
- Epstein, L., Favrholdt, L. M., and Kohrt, J. S. 2006. The relative worst order ratio applied to scheduling problems. J. Combin. Optim. 12, 362--385.Google ScholarCross Ref
- Graham, R. L. 1966. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563--1581.Google ScholarCross Ref
- Johnson, D. S. 1974. Fast algorithms for bin packing. J. Comput. Syst. Sci. 8, 272--314.Google ScholarDigital Library
- Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., and Graham, R. L. 1974. Worst-Case performance bound for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 299--325.Google ScholarCross Ref
- Karlin, A. R., Manasse, M. S., Rudolph, L., and Sleator, D. D. 1988. Competitive snoopy caching. Algorithmica 3, 1, 79--119.Google ScholarDigital Library
- Kenyon, C. 1996. Best-Fit bin-packing with random order. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 359--364. Google ScholarDigital Library
- Kohrt, J. S. 2004. Online algorithms under new assumptions. Ph.D. thesis, Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark.Google Scholar
- Krumke, S. O., de Paepe, W. E., Rambau, J., and Stougie, L. 2001. Online bin coloring. In Proceedings of the 9th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 2161. Springer Verlag, Berlin. 74--85. Google ScholarDigital Library
- Lee, C., and Lee, D. 1985. A simple on-line bin-packing algorithm. J. ACM 32, 3, 562--572. Google ScholarDigital Library
- Seiden, S. S. 2002. On the online bin packing problem. J. ACM 49, 5, 640--671. Google ScholarDigital Library
- Sleator, D. D., and Tarjan, R. E. 1985. Amortized efficiency of list update and paging rules. Commun. ACM 28, 2, 202--208. Google ScholarDigital Library
Index Terms
- The relative worst order ratio for online algorithms
Recommendations
The maximum resource bin packing problem
Usually, for bin packing problems, we try to minimize the number of bins used or in the case of the dual bin packing problem, maximize the number or total size of accepted items. This paper presents results for the opposite problems, where we would like ...
Fair versus Unrestricted Bin Packing
Abstract. We consider the on-line Dual Bin Packing problem where we have nunit size bins and a sequence of items. The goal is to maximize the number of items that are packed in the bins by an on-line algorithm. We investigate unrestrictedalgorithms ...
The relative worst order ratio applied to seat reservation
The seat reservation problem is the problem of assigning passengers to seats on a train with n seats and k stations enroute in an online manner. The performance of algorithms for this problem is studied using the relative worst order ratio, a fairly new ...
Comments