{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:10:18Z","timestamp":1740103818750,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T00:00:00Z","timestamp":1500508800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"The Danish Council for Independent Research","award":["DFF-1323-00247"],"award-info":[{"award-number":["DFF-1323-00247"]}]},{"DOI":"10.13039\/100008398","name":"The Villum Foundation","doi-asserted-by":"crossref","award":["VKR-23219"],"award-info":[{"award-number":["VKR-23219"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s10951-017-0536-y","type":"journal-article","created":{"date-parts":[[2017,7,20]],"date-time":"2017-07-20T14:54:59Z","timestamp":1500562499000},"page":"429-441","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online-bounded analysis"],"prefix":"10.1007","volume":"21","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leah","family":"Epstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0560-3794","authenticated-orcid":false,"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Asaf","family":"Levin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,20]]},"reference":[{"key":"536_CR1","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/PL00009158","volume":"18","author":"S Albers","year":"1997","unstructured":"Albers, S. (1997). On the influence of lookahead in competitive paging algorithms. Algorithmica, 18, 283\u2013305.","journal-title":"Algorithmica"},{"issue":"2","key":"536_CR2","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.jcss.2004.08.002","volume":"70","author":"S Albers","year":"2005","unstructured":"Albers, S., Favrholdt, L. M., & Giel, O. (2005). On paging with locality of reference. Journal of Computer and System Sciences, 70(2), 145\u2013175.","journal-title":"Journal of Computer and System Sciences"},{"key":"536_CR3","unstructured":"Angelopoulos, S., Dorrigiv, R., & L\u00f3pez-Ortiz, A. (2007). On the separation and equivalence of paging strategies. In 18th ACM\u2013SIAM symposium on discrete algorithms (SODA) (pp. 229\u2013237)"},{"issue":"2","key":"536_CR4","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-002-0965-6","volume":"34","author":"Y Azar","year":"2002","unstructured":"Azar, Y., Boyar, J., Epstein, L., Favrholdt, L. M., Larsen, K. S., & Nielsen, M. N. (2002). Fair versus unrestricted bin packing. Algorithmica, 34(2), 181\u2013196.","journal-title":"Algorithmica"},{"issue":"2","key":"536_CR5","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1002\/(SICI)1099-1425(199808)1:2<67::AID-JOS6>3.0.CO;2-Y","volume":"1","author":"Y Azar","year":"1998","unstructured":"Azar, Y., & Epstein, L. (1998). On-line machine covering. Journal of Scheduling, 1(2), 67\u201377.","journal-title":"Journal of Scheduling"},{"issue":"1","key":"536_CR6","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0304-3975(00)00258-9","volume":"268","author":"Y Azar","year":"2001","unstructured":"Azar, Y., & Regev, O. (2001). On-line bin-stretching. Theoretical Computer Science, 268(1), 17\u201341.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"536_CR7","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1023\/A:1022985808959","volume":"6","author":"E Bach","year":"2003","unstructured":"Bach, E., Boyar, J., Epstein, L., Favrholdt, L. M., Jiang, T., Larsen, K. S., et al. (2003). Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem. Journal of Scheduling, 6(2), 131\u2013147.","journal-title":"Journal of Scheduling"},{"key":"536_CR8","doi-asserted-by":"crossref","unstructured":"Bansal, N., & Sviridenko, M. (2006). The Santa Claus problem. In 38th annual ACM symposium on the theory of computing (STOC) (pp. 31\u201340)","DOI":"10.1145\/1132516.1132522"},{"issue":"1","key":"536_CR9","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"},{"issue":"2","key":"536_CR10","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1006\/jcss.1995.1021","volume":"50","author":"A Borodin","year":"1995","unstructured":"Borodin, A., Irani, S., Raghavan, P., & Schieber, B. (1995). Competitive paging with locality of reference. Journal of Computer and System Sciences, 50(2), 244\u2013258.","journal-title":"Journal of Computer and System Sciences"},{"key":"536_CR11","unstructured":"Boyar, J., Favrholdt, L., Mikkelsen, J., & Kudahl, C. (2015). Advice complexity for a class of online problems. In 32nd international symposium on theoretical aspects of computer science (STACS), Leibniz international proceedings in informatics (Vol. 30) (pp. 116\u2013129)."},{"key":"536_CR12","doi-asserted-by":"crossref","unstructured":"Boyar, J., & Favrholdt, L. M. (2007). The relative worst order ratio for on-line algorithms. ACM Transactions on Algorithms, 3(2), article 22, 24 p.","DOI":"10.1145\/1240233.1240245"},{"issue":"1","key":"536_CR13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00236-003-0124-9","volume":"40","author":"J Boyar","year":"2003","unstructured":"Boyar, J., Favrholdt, L. M., Larsen, K. S., & Nielsen, M. N. (2003). Extending the accommodating function. Acta Informatica, 40(1), 3\u201335.","journal-title":"Acta Informatica"},{"key":"536_CR14","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/PL00009286","volume":"25","author":"J Boyar","year":"1999","unstructured":"Boyar, J., & Larsen, K. (1999). The seat reservation problem. Algorithmica, 25, 403\u2013417.","journal-title":"Algorithmica"},{"issue":"1","key":"536_CR15","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1137\/S0097539799361786","volume":"31","author":"J Boyar","year":"2001","unstructured":"Boyar, J., Larsen, K. S., & Nielsen, M. N. (2001). The accommodating function\u2014A generalization of the competitive ratio. SIAM Journal on Computing, 31(1), 233\u2013258.","journal-title":"SIAM Journal on Computing"},{"issue":"1\u20132","key":"536_CR16","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0304-3975(98)00118-2","volume":"209","author":"D Breslauer","year":"1998","unstructured":"Breslauer, D. (1998). On competitive on-line paging with lookahead. Theoretical Computer Science, 209(1\u20132), 365\u2013375.","journal-title":"Theoretical Computer Science"},{"key":"536_CR17","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-3-642-22006-7_19","volume-title":"Automata, languages and programming (ICALP), LNCS","author":"SH Chan","year":"2011","unstructured":"Chan, S. H., Lam, T. W., Lee, L. K., Liu, C. M., & Ting, H. F. (2011). Sleep management on multiple machines for energy and flow time. In L. Aceto, M. Henzinger, & J. Sgall (Eds.), Automata, languages and programming (ICALP), LNCS (Vol. 6755, pp. 219\u2013231). Berlin: Springer."},{"issue":"1","key":"536_CR18","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 Journal on Computing, 9(1), 91\u2013103.","journal-title":"SIAM Journal on Computing"},{"key":"536_CR19","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(88)90052-2","volume":"21","author":"J Csirik","year":"1988","unstructured":"Csirik, J., & Totik, V. (1988). On-line algorithms for a dual version of bin packing. Discrete Applied Mathematics, 21, 163\u2013167.","journal-title":"Discrete Applied Mathematics"},{"key":"536_CR20","doi-asserted-by":"crossref","first-page":"3694","DOI":"10.1016\/j.tcs.2009.04.023","volume":"410","author":"R Dorrigiv","year":"2009","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A., & Munro, J. I. (2009). On the relative dominance of paging algorithms. Theoretical Computer Science, 410, 3694\u20133701.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"536_CR21","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s00453-012-9637-3","volume":"66","author":"MR Ehmsen","year":"2013","unstructured":"Ehmsen, M. R., Kohrt, J. S., & Larsen, K. S. (2013). List factoring and relative worst order analysis. Algorithmica, 66(2), 287\u2013309.","journal-title":"Algorithmica"},{"issue":"2","key":"536_CR22","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.dam.2005.02.002","volume":"148","author":"L Epstein","year":"2005","unstructured":"Epstein, L. (2005). Tight bounds for bandwidth allocation on two links. Discrete Applied Mathematics, 148(2), 181\u2013188.","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"536_CR23","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s10878-006-9005-9","volume":"12","author":"L Epstein","year":"2006","unstructured":"Epstein, L., Favrholdt, L. M., & Kohrt, J. S. (2006). Separating online scheduling algorithms with the relative worst order ratio. Journal of Combinatorial Optimization, 12(4), 363\u2013386.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"2","key":"536_CR24","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, S. S., Sgall, J., & Woeginger, G. J. (2001). Randomized online scheduling on two uniform machines. Journal of Scheduling, 4(2), 71\u201392.","journal-title":"Journal of Scheduling"},{"key":"536_CR25","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2014.09.011","volume":"562","author":"Y Giannakopoulos","year":"2015","unstructured":"Giannakopoulos, Y., & Koutsoupias, E. (2015). Competitive analysis of maintaining frequent items of a stream. Theoretical Computer Science, 562, 23\u201332.","journal-title":"Theoretical Computer Science"},{"key":"536_CR26","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, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell Systems Technical Journal, 45, 1563\u20131581.","journal-title":"Bell Systems Technical Journal"},{"issue":"4","key":"536_CR27","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., & Pruhs, K. (2000). Speed is as powerful as clairvoyance. Journal of the ACM, 47(4), 617\u2013643.","journal-title":"Journal of the ACM"},{"key":"536_CR28","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin, A. R., Manasse, M. S., Rudolph, L., & Sleator, D. D. (1988). Competitive snoopy caching. Algorithmica, 3, 79\u2013119.","journal-title":"Algorithmica"},{"key":"536_CR29","doi-asserted-by":"crossref","unstructured":"Karlin, A. R., Phillips, S. J., & Raghavan, P. (2000). Markov paging. SIAM Journal on Computing, 30(3), 906\u2013922.","DOI":"10.1137\/S0097539794268042"},{"key":"536_CR30","unstructured":"Kenyon, C. (1996). Best-fit bin-packing with random order. In 7th ACM-SIAM symposium on discrete algorithms (SODA) (pp. 359\u2013364)"},{"issue":"1","key":"536_CR31","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E Koutsoupias","year":"2000","unstructured":"Koutsoupias, E., & Papadimitriou, C. H. (2000). Beyond competitive analysis. SIAM Journal on Computing, 30(1), 300\u2013317.","journal-title":"SIAM Journal on Computing"},{"key":"536_CR32","doi-asserted-by":"crossref","unstructured":"Miyazaki, S., & Okamoto, K. (2010). Improving the competitive ratios of the seat reservation problem. In 6th IFIP TC 1\/WG 2.2 international conference on theoretical computer science (IFIP TCS), IFIP advances in information and communication technology (Vol. 323) (pp. 328\u2013339). Springer.","DOI":"10.1007\/978-3-642-15240-5_24"},{"key":"536_CR33","doi-asserted-by":"crossref","unstructured":"Raghavan, P. (1992). A statistical adversary for on-line algorithms. In On-line algorithms, Series in discrete mathematics and theoretical computer science (Vol. 7) (pp. 79\u201383). American Mathematical Society.","DOI":"10.1090\/dimacs\/007\/05"},{"issue":"2","key":"536_CR34","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D. D., & Tarjan, R. E. (1985). Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2), 202\u2013208.","journal-title":"Communications of the ACM"},{"issue":"4","key":"536_CR35","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0167-6377(96)00055-7","volume":"20","author":"GJ Woeginger","year":"1997","unstructured":"Woeginger, G. J. (1997). A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20(4), 149\u2013154.","journal-title":"Operations Research Letters"},{"key":"536_CR36","unstructured":"Young, N. (1991). Competitive paging and dual-guided algorithms for weighted caching and matching (thesis). Tech. rep. CS-TR-348-91, Computer Science Department, Princeton University."},{"key":"536_CR37","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"NE Young","year":"1994","unstructured":"Young, N. E. (1994). The $$k$$ k -server dual and loose competitiveness for paging. Algorithmica, 11, 525\u2013541.","journal-title":"Algorithmica"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-017-0536-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-017-0536-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-017-0536-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T01:22:59Z","timestamp":1569892979000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-017-0536-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,20]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["536"],"URL":"https:\/\/doi.org\/10.1007\/s10951-017-0536-y","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2017,7,20]]}}}