{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T20:09:36Z","timestamp":1672603776411},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,6,26]],"date-time":"2018-06-26T00:00:00Z","timestamp":1529971200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1007\/s00453-018-0461-2","type":"journal-article","created":{"date-parts":[[2018,6,26]],"date-time":"2018-06-26T12:57:50Z","timestamp":1530017870000},"page":"1152-1179","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Separation and Equivalence of Paging Strategies and Other Online Algorithms"],"prefix":"10.1007","volume":"81","author":[{"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reza","family":"Dorrigiv","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,26]]},"reference":[{"issue":"3","key":"461_CR1","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/PL00009158","volume":"18","author":"S Albers","year":"1997","unstructured":"Albers, S.: On the influence of lookahead in competitive paging algorithms. Algorithmica 18(3), 283\u2013305 (1997)","journal-title":"Algorithmica"},{"issue":"3","key":"461_CR2","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":"461_CR3","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."},{"issue":"5","key":"461_CR4","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1016\/j.jcss.2015.11.005","volume":"82","author":"S Albers","year":"2016","unstructured":"Albers, S., Lauer, S.: On list update with locality of reference. J. Comput. Syst. Sci. 82(5), 627\u2013653 (2016)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"461_CR5","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/PL00009217","volume":"21","author":"S Albers","year":"1998","unstructured":"Albers, S., Mitzenmacher, M.: Average case analyses of list update algorithms, with applications to data compression. Algorithmica 21(3), 312\u2013329 (1998)","journal-title":"Algorithmica"},{"key":"461_CR6","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. Proces. Lett. 56, 135\u2013139 (1995)","journal-title":"Inf. Proces. Lett."},{"key":"461_CR7","doi-asserted-by":"crossref","unstructured":"Albers, S., Westbrook, J.: Self-organizing data structures. In: Online Algorithms: The State of the Art. Lecture Notes in Computer Science 1442, pp. 13\u201351. Springer (1998)","DOI":"10.1007\/BFb0029563"},{"issue":"4","key":"461_CR8","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/2500120","volume":"9","author":"C Amb\u00fchl","year":"2013","unstructured":"Amb\u00fchl, C., G\u00e4rtner, B., von Stengel, B.: Optimal lower bounds for projective list update algorithms. ACM Trans. Algorithms 9(4), 31 (2013)","journal-title":"ACM Trans. Algorithms"},{"key":"461_CR9","unstructured":"Angelopoulos. S.: Parameterized analysis of online Steiner tree problems. In: Adaptive, Output Sensitive, Online and Parameterized Algorithms, number 09171 in Dagstuhl Seminar Proceedings. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Germany (2009)"},{"key":"461_CR10","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-Ortiz, A.: List update with locality of reference. In: Proceedings of the 8th Latin American Symposium on Theoretical Informatics, pp. 399\u2013410 (2008)","DOI":"10.1007\/978-3-540-78773-0_35"},{"key":"461_CR11","unstructured":"Angelopoulos, S., Renault, M., Schweitzer, P.: Stochastic dominance and the bijective ratio of online algorithms (2016). arXiv:1607.06132"},{"issue":"2","key":"461_CR12","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/2450142.2450143","volume":"60","author":"S Angelopoulos","year":"2013","unstructured":"Angelopoulos, S., Schweitzer, P.: Paging and list update under bijective analysis. J. ACM 60(2), 7 (2013)","journal-title":"J. ACM"},{"issue":"2","key":"461_CR13","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00453-001-0069-8","volume":"32","author":"R Bachrach","year":"2002","unstructured":"Bachrach, R., El-Yaniv, R., Reinst\u00e4dler, M.: On the competitive theory and practice of online list accessing algorithms. Algorithmica 32(2), 201\u2013245 (2002)","journal-title":"Algorithmica"},{"key":"461_CR14","doi-asserted-by":"crossref","unstructured":"Becchetti, L.: Modeling locality: A probabilistic analysis of LRU and FWF. In: Proceedings of the 12th Annual European Symposium on Algorithms (ESA \u201904), volume 3221 of Lecture Notes in Computer Science, pp. 98\u2013109 (2004)","DOI":"10.1007\/978-3-540-30140-0_11"},{"key":"461_CR15","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, 73\u201391 (1994)","journal-title":"Algorithmica"},{"key":"461_CR16","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)"},{"key":"461_CR17","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, 244\u2013258 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"7\u20138","key":"461_CR18","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":"2","key":"461_CR19","doi-asserted-by":"crossref","first-page":"22","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. Trans. Algorithms 3(2), 22 (2007)","journal-title":"Trans. Algorithms"},{"issue":"5","key":"461_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":"461_CR21","doi-asserted-by":"crossref","unstructured":"Boyar, J., Gupta, S., Larsen, K.S.: Access graph results for LRU versus FIFO under relative worst order analysis. In: Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 328\u2013339 (2012)","DOI":"10.1007\/978-3-642-31155-0_29"},{"key":"461_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":"461_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"},{"key":"461_CR24","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":"461_CR25","doi-asserted-by":"publisher","first-page":"48","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), 48 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"461_CR26","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/PL00009166","volume":"18","author":"WR Burley","year":"1997","unstructured":"Burley, W.R., Irani, S.: On algorithm design for metrical task systems. Algorithmica 18(4), 461\u2013485 (1997)","journal-title":"Algorithmica"},{"key":"461_CR27","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical Report 124, DEC SRC (1994)"},{"issue":"2","key":"461_CR28","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"},{"issue":"5","key":"461_CR29","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":"38\u201340","key":"461_CR30","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, Alejandro A., Munro, J.I.: On the relative dominance of paging algorithms. Theor. Comput. Sci. 410(38\u201340), 3694\u20133701 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"461_CR31","first-page":"67","volume":"36","author":"R Dorrigiv","year":"2005","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A.: A survey of performance measures for on-line algorithms. SIGACT News (ACM Special Interest Group on Automata and Computability Theory) 36(3), 67\u201381 (2005)","journal-title":"SIGACT News (ACM Special Interest Group on Automata and Computability Theory)"},{"issue":"13","key":"461_CR32","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1016\/j.ipl.2012.04.002","volume":"112","author":"R Dorrigiv","year":"2012","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A.: List update with probabilistic locality of reference. Inf. Process. Lett. 112(13), 540\u2013543 (2012)","journal-title":"Inf. Process. Lett."},{"key":"461_CR33","unstructured":"El-Yaniv, R.: There are infinitely many competitive-optimal online list accessing algorithms. Discussion paper, Hebrew University of Jerusalem, Center for Rationality and Interactive Decision Theory (1996)"},{"issue":"3","key":"461_CR34","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1145\/5505.5507","volume":"17","author":"JH Hester","year":"1985","unstructured":"Hester, J.H., Hirschberg, D.S.: Self-organizing linear search. ACM Comput. Surv. 17(3), 295 (1985)","journal-title":"ACM Comput. Surv."},{"key":"461_CR35","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, 301\u2013306 (1991)","journal-title":"Inf. Process. Lett."},{"key":"461_CR36","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/S0097539792236353","volume":"25","author":"S Irani","year":"1996","unstructured":"Irani, S., Karlin, A.R., Phillips, S.: Strongly competitive algorithms for paging with locality of reference. SIAM J. Comput. 25, 477\u2013497 (1996)","journal-title":"SIAM J. Comput."},{"key":"461_CR37","doi-asserted-by":"crossref","unstructured":"Kamali, S., L\u00f3pez-Ortiz, A.: A survey of algorithms and models for list update. In: Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pp. 251\u2013266 (2013)","DOI":"10.1007\/978-3-642-40273-9_17"},{"issue":"3","key":"461_CR38","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.tcs.2007.07.020","volume":"387","author":"H Kaplan","year":"2007","unstructured":"Kaplan, H., Landau, S., Verbin, E.: A simpler analysis of Burrows-Wheeler based compression. Theor. Comput. Sci. 387(3), 220\u2013235 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"461_CR39","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1137\/S0097539794268042","volume":"30","author":"AR Karlin","year":"2000","unstructured":"Karlin, A.R., Phillips, S.J., Raghavan, P.: Markov paging. SIAM J. Comput. 30(3), 906\u2013922 (2000)","journal-title":"SIAM J. Comput."},{"key":"461_CR40","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: ACM-SIAM SODA \u201996, pp. 359\u2013364 (1996)"},{"key":"461_CR41","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E Koutsoupias","year":"2000","unstructured":"Koutsoupias, E., Papadimitriou, C.: Beyond competitive analysis. SIAM J. Comput. 30, 300\u2013317 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"461_CR42","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0304-3975(98)00264-3","volume":"242","author":"C Mart\u00ednez","year":"2000","unstructured":"Mart\u00ednez, C., Roura, S.: On the competitiveness of the move-to-front rule. Theor. Comput. Sci. 242(1\u20132), 313\u2013325 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"461_CR43","unstructured":"Megiddo, N., Modha, D.S.: ARC: A self-tuning, low overhead replacement cache. In: Proceedings of the FAST \u201903 Conference on File and Storage Technologies (2003)"},{"key":"461_CR44","doi-asserted-by":"crossref","unstructured":"Munro, J.I.: On the competitiveness of linear search. In: Proceedings of the 8th Annual European Symposium on Algorithms (ESA \u201900). volume 1879 of Lecture Notes in Computer Science, pp. 338\u2013345 (2000)","DOI":"10.1007\/3-540-45253-2_31"},{"issue":"1","key":"461_CR45","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1145\/300515.300518","volume":"46","author":"EJ O\u2019Neil","year":"1999","unstructured":"O\u2019Neil, E.J., O\u2019Neil, P.E., Weikum, G.: An optimality proof of the LRU-K page replacement algorithm. J. ACM 46(1), 92\u2013112 (1999)","journal-title":"J. ACM"},{"key":"461_CR46","doi-asserted-by":"crossref","unstructured":"Panagiotou, K., Souza, A.: On adequate performance measures for paging. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC \u201906), pp. 487\u2013496 (2006)","DOI":"10.1145\/1132516.1132587"},{"key":"461_CR47","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF01294261","volume":"11","author":"N Reingold","year":"1994","unstructured":"Reingold, N., Westbrook, J., Sleator, D.D.: Randomized competitive algorithms for the list update problem. Algorithmica 11, 15\u201332 (1994)","journal-title":"Algorithmica"},{"key":"461_CR48","unstructured":"Schulz, F.: Two new families of list update algorithms. In: Proceedings of the 9th International Symposium on Algorithms and Computation (ISAAC \u201998), volume 1533 of Lecture Notes in Computer Science, pp. 99\u2013108. Springer (1998)"},{"key":"461_CR49","volume-title":"Operating System Concepts","author":"A Silberschatz","year":"2002","unstructured":"Silberschatz, A., Galvin, P.B., Gagne, G.: Operating System Concepts. Wiley, Hoboken (2002)"},{"key":"461_CR50","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, 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"issue":"2","key":"461_CR51","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/PL00009192","volume":"20","author":"E Torng","year":"1998","unstructured":"Torng, E.: A unified analysis of paging and caching. Algorithmica 20(2), 175\u2013200 (1998)","journal-title":"Algorithmica"},{"key":"461_CR52","unstructured":"Witten, I.H., Bell, T.: The Calgary\/Canterbury text compression corpus. https:\/\/urldefense.proofpoint.com\/v2\/url?u=http-3A__corpus.canterbury.ac.nz_resources_calgary.tar.gz&d=DwICAg&c=vh6FgFnduejNhPPD0fl_yRaSfZy8CWbWnIf4XJhSqx8&r=cijxKIUfIjh6xB35XSxKelnSNfz2185wGO_qFr-DFH8&m=J6RYYpZfpyF_ohIicn6Ok991AGPobbkIOD5buCQJ29Q&s=oH14Kym57oZMk1NpzUHa6ZqQhtV-amaWVPNHH-WJ7-k&e="},{"issue":"6","key":"461_CR53","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"NE Young","year":"1994","unstructured":"Young, N.E.: The $$k$$ k -server dual and loose competitiveness for paging. Algorithmica 11(6), 525\u2013541 (1994)","journal-title":"Algorithmica"},{"key":"461_CR54","unstructured":"Young, N.E.: Bounding the diffuse adversary. In: Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA \u201998), pp. 420\u2013425 (1998)"},{"issue":"1","key":"461_CR55","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1006\/jagm.2000.1099","volume":"37","author":"NE Young","year":"2000","unstructured":"Young, N.E.: On-line paging against adversarially biased random inputs. J. Algorithms 37(1), 218\u2013235 (2000)","journal-title":"J. Algorithms"},{"issue":"3","key":"461_CR56","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s00453-001-0124-5","volume":"33","author":"NE Young","year":"2002","unstructured":"Young, N.E.: On-line file caching. Algorithmica 33(3), 371\u2013383 (2002)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0461-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0461-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0461-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T09:21:13Z","timestamp":1604481673000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0461-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,26]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["461"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0461-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,26]]},"assertion":[{"value":"11 February 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}