{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:43:24Z","timestamp":1710351804252},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2006,9,20]],"date-time":"2006-09-20T00:00:00Z","timestamp":1158710400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2006,10,21]]},"DOI":"10.1007\/s10878-006-9005-9","type":"journal-article","created":{"date-parts":[[2006,10,8]],"date-time":"2006-10-08T11:24:17Z","timestamp":1160306657000},"page":"363-386","source":"Crossref","is-referenced-by-count":19,"title":["Separating online scheduling algorithms with the relative worst order ratio"],"prefix":"10.1007","volume":"12","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[]},{"given":"Jens S.","family":"Kohrt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,9,20]]},"reference":[{"issue":"2","key":"9005_CR1","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1137\/S0097539797324874","volume":"29","author":"S Albers","year":"1999","unstructured":"Albers S (1999) Better bounds for online scheduling. SIAM J Comput 29(2):459\u2013473","journal-title":"SIAM J Comput"},{"issue":"3","key":"9005_CR2","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1006\/jcss.1995.1074","volume":"51","author":"Y Bartal","year":"1995","unstructured":"Bartal Y, Fiat A, Karloff H, Vohra R (1995) New algorithms for an ancient scheduling problem. J Comput Syst Sci 51(3):359\u2013366","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"9005_CR3","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"S Ben-David","year":"1994","unstructured":"Ben-David S, Borodin A (1994) A new measure for the study of on-line algorithms. Algorithmica 11(1):73\u201391","journal-title":"Algorithmica"},{"key":"9005_CR4","doi-asserted-by":"crossref","unstructured":"Boyar J, Favrholdt LM (2003) The relative worst order ratio for on-line algorithms. In Proc. 5th Italian conf. on algorithms and complexity, vol. 2653 of Lect Notes Comp Sci Springer-Verlag, pp 58\u201369","DOI":"10.1007\/3-540-44849-7_13"},{"key":"9005_CR5","unstructured":"Boyar J, Favrholdt LM, Larsen KS (2005) The relative worst order ratio applied to paging. In Proc. 16th Annu. ACM-SIAM symp. discrete algorithms, pp 718\u2013727"},{"key":"9005_CR6","doi-asserted-by":"crossref","unstructured":"Boyar J, Medvedev P (2004) The relative worst order ratio applied to seat reservation. In Proc. of the 9th scand. workshop on algorithm theory, vol. 3111 in Lect Notes Comp Sci pp 90\u2013101","DOI":"10.1007\/978-3-540-27810-8_9"},{"issue":"3","key":"9005_CR7","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0167-6377(95)00039-9","volume":"18","author":"B Chen","year":"1995","unstructured":"Chen B, van Vliet A, Woeginger GJ (1995) An optimal algorithm for preemptive on-line scheduling. Oper Res Lett 18(3):127\u2013131","journal-title":"Oper Res Lett"},{"issue":"1","key":"9005_CR8","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/0209007","volume":"9","author":"Y Cho","year":"1980","unstructured":"Cho Y, Sahni S (1980) Bounds for list schedules on uniform processors. SIAM J Comput 9(1):91\u2013103","journal-title":"SIAM J Comput"},{"issue":"2","key":"9005_CR9","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1002\/jos.60","volume":"4","author":"L Epstein","year":"2001","unstructured":"Epstein L, Noga J, Seiden SS, Sgall J, Woeginger GJ (2001) Randomized online scheduling on two uniform machines. J Sched 4(2):71\u201392","journal-title":"J Sched"},{"issue":"1","key":"9005_CR10","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0167-6377(99)00062-0","volume":"26","author":"L Epstein","year":"2000","unstructured":"Epstein L, Sgall J (2000) A lower bound for on-line scheduling on uniformly related machines. Oper Res Lett 26(1):17\u201322","journal-title":"Oper Res Lett"},{"issue":"2","key":"9005_CR11","first-page":"107","volume":"9","author":"U Faigle","year":"1989","unstructured":"Faigle U, Kern W, Tur\u00e4n G (1989) On the performance of on-line algorithms for partition problems. Acta Cybernet 9(2):107\u2013119","journal-title":"Acta Cybernet"},{"issue":"6","key":"9005_CR12","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2","volume":"3","author":"R Fleischer","year":"2000","unstructured":"Fleischer R, Wahl M (2000) On-line scheduling revisited. J Sched 3(6):343\u2013353","journal-title":"J Sched"},{"issue":"2","key":"9005_CR13","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1137\/0222026","volume":"22","author":"G Galambos","year":"1993","unstructured":"Galambos G, Woeginger GJ (1993) An on-line scheduling heuristic with better worst case ratio than Graham\u2019s list scheduling. SIAM J Comput 22(2):349\u2013355","journal-title":"SIAM J Comput"},{"issue":"1","key":"9005_CR14","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1145\/322047.322055","volume":"25","author":"T Gonzalez","year":"1978","unstructured":"Gonzalez T, Sahni S (1978) Preemptive scheduling of uniform processor systems. J ACM 25(1):92\u2013101","journal-title":"J ACM"},{"key":"9005_CR15","unstructured":"Gormley T, Reingold N, Torng E, Westbrook J (2000) Generating adversaries for request-answer games. In Proc. 11th annu. ACM-SIAM symp. on discrete algorithms, pp 564\u2013565"},{"key":"9005_CR16","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Systems Techn J 45:1563\u20131581","journal-title":"Bell Systems Techn J"},{"issue":"2","key":"9005_CR17","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jagm.1996.0019","volume":"20","author":"DR Karger","year":"1996","unstructured":"Karger DR, Philips SJ, Torng E (1996) A better algorithm for an ancient scheduling problem. J Algorithms 20(2):400\u2013430","journal-title":"J Algorithms"},{"key":"9005_CR18","unstructured":"Kenyon C (1996) Best-fit bin-packing with random order. In Proc. 7th annu. ACM-SIAM symp. on discrete algorithms, pp 359\u2013364"},{"key":"9005_CR19","unstructured":"Kohrt JS (2004) Online algorithms under new assumptions, PhD thesis, Dept Math and Comp Sci, Univ South Den, p. 78."},{"issue":"1","key":"9005_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R McNaughton","year":"1959","unstructured":"McNaughton R (1959) Scheduling with deadlines and loss functions. Manag Sci 6(1):1\u201312","journal-title":"Manag Sci"},{"issue":"1\u20132","key":"9005_CR21","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/S0304-3975(00)00288-7","volume":"262","author":"SS Seiden","year":"2001","unstructured":"Seiden SS (2001) Preemptive multiprocessor scheduling with rejection. Theoret Comp Sci 262(1\u20132):437\u2013458","journal-title":"Theoret Comp Sci"},{"key":"9005_CR22","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0167-6377(98)00032-7","volume":"23","author":"J Wen","year":"1998","unstructured":"Wen J, Du D (1998) Preemptive on-line scheduling for two uniform processors. Oper Res Lett 23:113\u2013116","journal-title":"Oper Res Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-9005-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-006-9005-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-9005-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:10Z","timestamp":1559276290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-006-9005-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9,20]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,10,21]]}},"alternative-id":["9005"],"URL":"https:\/\/doi.org\/10.1007\/s10878-006-9005-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9,20]]}}}