{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:17:17Z","timestamp":1742955437752,"version":"3.40.3"},"publisher-location":"Cham","reference-count":64,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319983547"},{"type":"electronic","value":"9783319983554"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98355-4_13","type":"book-chapter","created":{"date-parts":[[2018,8,8]],"date-time":"2018-08-08T10:34:57Z","timestamp":1533724497000},"page":"216-230","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Relative Worst-Order Analysis: A Survey"],"prefix":"10.1007","author":[{"given":"Joan","family":"Boyar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lene M.","family":"Favrholdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kim S.","family":"Larsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"issue":"3","key":"13_CR1","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1137\/S0097539794277858","volume":"27","author":"S Albers","year":"1998","unstructured":"Albers, S.: Improved randomized on-line algorithms for the list update problem. SIAM J. Comput. 27(3), 682\u2013693 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"13_CR2","doi-asserted-by":"publisher","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.: On paging with locality of reference. J. Comput. Syst. Sci. 70(2), 145\u2013175 (2005)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0020-0190(95)00142-Y","volume":"56","author":"S Albers","year":"1995","unstructured":"Albers, S., von Stengel, B., Werchner, R.: A combined BIT and TIMESTAMP algorithm for the list update problem. Inf. Process. Lett. 56, 135\u2013139 (1995)","journal-title":"Inf. Process. Lett."},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BFb0029563","volume-title":"Online Algorithms","author":"S Albers","year":"1998","unstructured":"Albers, S., Westbrook, J.: Self-organizing data structures. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms. LNCS, vol. 1442, pp. 13\u201351. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0029563"},{"key":"13_CR5","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-Ortiz, A.: On the separation and equivalence of paging strategies. In: 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 229\u2013237 (2007)"},{"key":"13_CR6","unstructured":"Angelopoulos, S., Renault, M.P., Schweitzer, P.: Stochastic dominance and the bijective ratio of online algorithms. arXiv arXiv:1607.06132 [cs.DS] (2016)"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-540-74208-1_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M Babaioff","year":"2007","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX\/RANDOM-2007. LNCS, vol. 4627, pp. 16\u201328. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74208-1_2"},{"key":"13_CR8","unstructured":"Bachrach, R., El-Yaniv, R.: Online list accessing algorithms and their applications: recent empirical evidence. In: 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 53\u201362 (1997)"},{"issue":"1","key":"13_CR9","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BF01294264","volume":"11","author":"S Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A.: A new measure for the study of on-line algorithms. Algorithmica 11(1), 73\u201391 (1994)","journal-title":"Algorithmica"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1145\/3341.3349","volume":"28","author":"JL Bentley","year":"1985","unstructured":"Bentley, J.L., McGeoch, C.C.: Amortized analyses of self-organizing sequential search heuristics. Commun. ACM 28, 404\u2013411 (1985)","journal-title":"Commun. ACM"},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ic.2017.03.001","volume":"254","author":"H-J B\u00f6ckenhauer","year":"2017","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovic, R., Kr\u00e1lovic, R., M\u00f6mke, T.: Online algorithms with advice: the tape model. Inf. Comput. 254, 59\u201383 (2017)","journal-title":"Inf. Comput."},{"key":"13_CR12","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"issue":"2","key":"13_CR13","doi-asserted-by":"publisher","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.: Competitive paging with locality of reference. J. Comput. Syst. Sci. 50(2), 244\u2013258 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"7\u20138","key":"13_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s00236-010-0123-6","volume":"47","author":"J Boyar","year":"2010","unstructured":"Boyar, J., Ehmsen, M.R., Kohrt, J.S., Larsen, K.S.: A theoretical comparison of LRU and LRU-K. Acta Inf. 47(7\u20138), 359\u2013374 (2010)","journal-title":"Acta Inf."},{"issue":"4","key":"13_CR15","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s10951-017-0536-y","volume":"21","author":"J Boyar","year":"2018","unstructured":"Boyar, J., Epstein, L., Favrholdt, L.M., Larsen, K.S., Levin, A.: Online-bounded analysis. J. Sched. 21(4), 429\u2013441 (2018)","journal-title":"J. Sched."},{"issue":"26\u201328","key":"13_CR16","doi-asserted-by":"publisher","first-page":"2572","DOI":"10.1016\/j.tcs.2010.03.019","volume":"411","author":"J Boyar","year":"2010","unstructured":"Boyar, J., Epstein, L., Levin, A.: Tight results for Next Fit and Worst Fit with resource augmentation. Theor. Comput. Sci. 411(26\u201328), 2572\u20132580 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"13_CR17","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/1240233.1240245","volume":"3","author":"J Boyar","year":"2007","unstructured":"Boyar, J., Favrholdt, L.M.: The relative worst order ratio for on-line algorithms. ACM Trans. Algorithms 3(2), 24 (2007). Article 22","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"13_CR18","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1007\/s00453-008-9257-0","volume":"57","author":"J Boyar","year":"2010","unstructured":"Boyar, J., Favrholdt, L.M.: Scheduling jobs on grid processors. Algorithmica 57(4), 819\u2013847 (2010)","journal-title":"Algorithmica"},{"issue":"2","key":"13_CR19","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/3056461","volume":"50","author":"J Boyar","year":"2017","unstructured":"Boyar, J., Favrholdt, L.M., Kudahl, C., Larsen, K.S., Mikkelsen, J.W.: Online algorithms with advice: a survey. ACM Comput. Surv. 50(2), 19:1\u201319:34 (2017)","journal-title":"ACM Comput. Surv."},{"issue":"5","key":"13_CR20","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1016\/j.jcss.2007.03.001","volume":"73","author":"J Boyar","year":"2007","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S.: The relative worst order ratio applied to paging. J. Comput. Syst. Sci. 73(5), 818\u2013843 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-31155-0_29","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"J Boyar","year":"2012","unstructured":"Boyar, J., Gupta, S., Larsen, K.S.: Access graphs results for LRU versus FIFO under relative worst order analysis. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 328\u2013339. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31155-0_29"},{"key":"13_CR22","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.tcs.2014.11.035","volume":"568","author":"J Boyar","year":"2015","unstructured":"Boyar, J., Gupta, S., Larsen, K.S.: Relative interval analysis of paging algorithms on access graphs. Theor. Comput. Sci. 568, 28\u201348 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"13_CR23","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1007\/s00453-014-9884-6","volume":"72","author":"J Boyar","year":"2015","unstructured":"Boyar, J., Irani, S., Larsen, K.S.: A comparison of performance measures for online algorithms. Algorithmica 72(4), 969\u2013994 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"13_CR24","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/PL00009286","volume":"25","author":"J Boyar","year":"1999","unstructured":"Boyar, J., Larsen, K.S.: The seat reservation problem. Algorithmica 25(4), 403\u2013417 (1999)","journal-title":"Algorithmica"},{"key":"13_CR25","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2013.07.022","volume":"532","author":"J Boyar","year":"2014","unstructured":"Boyar, J., Larsen, K.S., Maiti, A.: A comparison of performance measures via online search. Theor. Comput. Sci. 532, 2\u201313 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"13_CR26","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1142\/S0129054115500239","volume":"26","author":"J Boyar","year":"2015","unstructured":"Boyar, J., Larsen, K.S., Maiti, A.: The frequent items problem in online streaming under various performance measures. Int. J. Found. Comput. Sci. 26(4), 413\u2013440 (2015)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"13_CR27","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1137\/S0097539799361786","volume":"31","author":"J Boyar","year":"2001","unstructured":"Boyar, J., Larsen, K.S., Nielsen, M.N.: The accommodating function: a generalization of the competitive ratio. SIAM J. Comput. 31(1), 233\u2013258 (2001)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"13_CR28","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/1383369.1383379","volume":"4","author":"J Boyar","year":"2008","unstructured":"Boyar, J., Medvedev, P.: The relative worst order ratio applied to seat reservation. ACM Trans. Algorithms 4(4), 22 (2008). Article 48","journal-title":"ACM Trans. Algorithms"},{"key":"13_CR29","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.tcs.2014.06.029","volume":"556","author":"MG Christ","year":"2014","unstructured":"Christ, M.G., Favrholdt, L.M., Larsen, K.S.: Online bin covering: expectations vs guarantees. Theor. Comput. Sci. 556, 71\u201384 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"13_CR30","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Karloff, H.J., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discret. Math. 4(2), 172\u2013181 (1991)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"13_CR31","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/PL00009255","volume":"23","author":"M Chrobak","year":"1999","unstructured":"Chrobak, M., Noga, J.: LRU is better than FIFO. Algorithmica 23(2), 180\u2013185 (1999)","journal-title":"Algorithmica"},{"key":"13_CR32","doi-asserted-by":"publisher","first-page":"2810","DOI":"10.1016\/j.dam.2007.11.004","volume":"156","author":"EG Coffmand Jr","year":"2008","unstructured":"Coffmand Jr., E.G., Csirik, J., R\u00f3nyai, L., Zsb\u00e1n, A.: Random-order bin packing. Discrete Appl. Math. 156, 2810\u20132816 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"13_CR33","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1145\/363095.363141","volume":"11","author":"PJ Denning","year":"1968","unstructured":"Denning, P.J.: The working set model for program behaviour. Commun. ACM 11(5), 323\u2013333 (1968)","journal-title":"Commun. ACM"},{"issue":"1","key":"13_CR34","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1109\/TSE.1980.230464","volume":"6","author":"PJ Denning","year":"1980","unstructured":"Denning, P.J.: Working sets past and present. IEEE Trans. Softw. Eng. 6(1), 64\u201384 (1980)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"13_CR35","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: 10th ACM Conference on Electronic Commerce (EC), pp. 71\u201378 (2009)","DOI":"10.1145\/1566374.1566384"},{"issue":"3","key":"13_CR36","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1051\/ita\/2009012","volume":"43","author":"S Dobrev","year":"2009","unstructured":"Dobrev, S., Kralovi\u0107, R., Pardubsk\u01ce, D.: Measuring the problem-relevant information in input. RAIRO - Theor. Inf. Appl. 43(3), 585\u2013613 (2009)","journal-title":"RAIRO - Theor. Inf. Appl."},{"key":"13_CR37","doi-asserted-by":"publisher","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.: On the relative dominance of paging algorithms. Theor. Comput. Sci. 410, 3694\u20133701 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"13_CR38","doi-asserted-by":"publisher","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.: List factoring and relative worst order analysis. Algorithmica 66(2), 287\u2013309 (2013)","journal-title":"Algorithmica"},{"issue":"4","key":"13_CR39","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/s10878-006-9005-9","volume":"12","author":"L Epstein","year":"2006","unstructured":"Epstein, L., Favrholdt, L.M., Kohrt, J.S.: Separating scheduling algorithms with the relative worst order ratio. J. Comb. Optim. 12(4), 362\u2013385 (2006)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"13_CR40","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s10951-009-0129-5","volume":"15","author":"L Epstein","year":"2012","unstructured":"Epstein, L., Favrholdt, L.M., Kohrt, J.S.: Comparing online algorithms for bin packing problems. J. Sched. 15(1), 13\u201321 (2012)","journal-title":"J. Sched."},{"key":"13_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-3-662-49529-2_35","volume-title":"LATIN 2016: Theoretical Informatics","author":"C Fischer","year":"2016","unstructured":"Fischer, C., R\u00f6glin, H.: Probabilistic analysis of the dual Next-Fit algorithm for bin covering. In: Kranakis, E., Navarro, G., Ch\u00e1vez, E. (eds.) LATIN 2016. LNCS, vol. 9644, pp. 469\u2013482. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_35"},{"key":"13_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1007\/978-3-662-48350-3_57","volume-title":"Algorithms - ESA 2015","author":"O G\u00f6bel","year":"2015","unstructured":"G\u00f6bel, O., Kesselheim, T., T\u00f6nnis, A.: Online appointment scheduling in the random order model. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 680\u2013692. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_57"},{"key":"13_CR43","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 982\u2013991 (2008)"},{"issue":"2","key":"13_CR44","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"issue":"C","key":"13_CR45","first-page":"168","volume":"29","author":"A Gy\u00e1rf\u00e1s","year":"1990","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: First fit and on-line chromatic number of families of graphs. Ars Comb. 29(C), 168\u2013176 (1990)","journal-title":"Ars Comb."},{"key":"13_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-15155-2_3","volume-title":"Mathematical Foundations of Computer Science 2010","author":"J Hromkovi\u010d","year":"2010","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: Information complexity of online problems. In: Hlin\u011bn\u00fd, P., Ku\u010dera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 24\u201336. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15155-2_3"},{"issue":"6","key":"13_CR47","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0020-0190(91)90086-W","volume":"38","author":"S Irani","year":"1991","unstructured":"Irani, S.: Two results on the list update problem. Inf. Process. Lett. 38(6), 301\u2013306 (1991)","journal-title":"Inf. Process. Lett."},{"key":"13_CR48","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/S0022-0000(74)80026-7","volume":"8","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Fast algorithms for bin packing. J. Comput. Syst. Sci. 8, 272\u2013314 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR49","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1137\/0203025","volume":"3","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bound for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 299\u2013325 (1974)","journal-title":"SIAM J. Comput."},{"key":"13_CR50","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47, 617\u2013643 (2000)","journal-title":"J. ACM"},{"key":"13_CR51","doi-asserted-by":"publisher","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.: Competitive snoopy caching. Algorithmica 3, 79\u2013119 (1988)","journal-title":"Algorithmica"},{"key":"13_CR52","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: 7th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 359\u2013364 (1996)"},{"issue":"1","key":"13_CR53","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E Koutsoupias","year":"2000","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J. Comput. 30(1), 300\u2013317 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"13_CR54","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.tcs.2008.05.022","volume":"407","author":"SO Krumke","year":"2008","unstructured":"Krumke, S.O., de Paepe, W., Rambau, J., Stougie, L.: Bincoloring. Theor. Comput. Sci. 407(1\u20133), 231\u2013241 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"13_CR55","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1287\/opre.13.4.609","volume":"13","author":"J McCabe","year":"1965","unstructured":"McCabe, J.: On serial files with relocatable records. Oper. Res. 13(4), 609\u2013618 (1965)","journal-title":"Oper. Res."},{"key":"13_CR56","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 426\u2013433 (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"key":"13_CR57","doi-asserted-by":"crossref","unstructured":"Moruz, G., Negoescu, A.: Outperforming LRU via competitive analysis on parametrized inputs for paging. In: 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1669\u20131680 (2012)","DOI":"10.1137\/1.9781611973099.132"},{"key":"13_CR58","doi-asserted-by":"crossref","unstructured":"O\u2019Neil, E.J., O\u2019Neil, P.E., Weikum, G.: The LRU-K page replacement algorithm for database disk buffering. In: ACM SIGMOD International Conference on Management of Data, pp. 297\u2013306 (1993)","DOI":"10.1145\/170036.170081"},{"key":"13_CR59","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s10951-007-0019-7","volume":"11","author":"CJ Osborn","year":"2008","unstructured":"Osborn, C.J., Torng, E.: List\u2019s worst-average-case or WAC ratio. J. Sched. 11, 213\u2013215 (2008)","journal-title":"J. Sched."},{"key":"13_CR60","doi-asserted-by":"crossref","unstructured":"Raghavan, P.: A statistical adversary for on-line algorithms. In: On-Line Algorithms, DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, vol. 7, pp. 79\u201383. American Mathematical Society (1992)","DOI":"10.1090\/dimacs\/007\/05"},{"issue":"2","key":"13_CR61","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"issue":"3","key":"13_CR62","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/990308.990310","volume":"51","author":"DA Spielman","year":"2004","unstructured":"Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385\u2013463 (2004)","journal-title":"J. ACM"},{"key":"13_CR63","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0020-0190(93)90150-8","volume":"47","author":"B Teia","year":"1993","unstructured":"Teia, B.: A lower bound for randomized list update algorithms. Inf. Process. Lett. 47, 5\u20139 (1993)","journal-title":"Inf. Process. Lett."},{"key":"13_CR64","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"NE Young","year":"1994","unstructured":"Young, N.E.: The $$k$$-server dual and loose competitiveness for paging. Algorithmica 11, 525\u2013541 (1994)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Adventures Between Lower Bounds and Higher Altitudes"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98355-4_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:56:24Z","timestamp":1710348984000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-98355-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319983547","9783319983554"],"references-count":64,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98355-4_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"9 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}