{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T03:47:32Z","timestamp":1754020052974,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>\n            We define a new measure for the quality of online algorithms, the\n            <jats:italic>relative worst order ratio<\/jats:italic>\n            , 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.\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/1240233.1240245","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["The relative worst order ratio for online algorithms"],"prefix":"10.1145","volume":"3","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[{"name":"University of Southern Denmark, Odense M, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense M, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0965-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294264"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.06.001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.001"},{"key":"e_1_2_1_5_1","first-page":"463","article-title":"The competitive ratio for on-line dual bin packing with restricted input sequences","volume":"8","author":"Boyar J.","year":"2001","unstructured":"Boyar , J. , Favrholdt , L. M. , Larsen , K. S. , and Nielsen , M. N. 2001 a. The competitive ratio for on-line dual bin packing with restricted input sequences . Nordic J. Comput. 8 , 4, 463 -- 472 . 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.","journal-title":"Nordic J. Comput."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009286"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361786"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 9th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science","volume":"3111","author":"Boyar J.","unstructured":"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. 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."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-9005-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01709.x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80026-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0203025"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762111"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 359--364","author":"Kenyon C.","year":"1996","unstructured":"Kenyon , C. 1996 . Best-Fit bin-packing with random order . In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 359--364 . Kenyon, C. 1996. Best-Fit bin-packing with random order. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 359--364."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 9th Annual European Symposium on Algorithms. Lecture Notes in Computer Science","volume":"2161","author":"Krumke S. O.","unstructured":"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. 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."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3833"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585269"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240245","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1240233.1240245","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:08Z","timestamp":1750258328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240245"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1240233.1240245"],"URL":"https:\/\/doi.org\/10.1145\/1240233.1240245","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}