{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:21:29Z","timestamp":1750306889320,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,4,1]],"date-time":"2013-04-01T00:00:00Z","timestamp":1364774400000},"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":["J. ACM"],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:p>It has long been known that for the paging problem in its standard form, competitive analysis cannot adequately distinguish algorithms based on their performance: there exists a vast class of algorithms that achieve the same competitive ratio, ranging from extremely naive and inefficient strategies (such as Flush-When-Full), to strategies of excellent performance in practice (such as Least-Recently-Used and some of its variants). A similar situation arises in the list update problem: in particular, under the cost formulation studied by Mart\u00ednez and Roura [2000] and Munro [2000] every list update algorithm has, asymptotically, the same competitive ratio. Several refinements of competitive analysis, as well as alternative performance measures have been introduced in the literature, with varying degrees of success in narrowing this disconnect between theoretical analysis and empirical evaluation.<\/jats:p>\n          <jats:p>\n            In this article, we study these two fundamental online problems under the framework of\n            <jats:italic>bijective analysis<\/jats:italic>\n            [Angelopoulos et al. 2007, 2008]. This is an intuitive technique that is based on pairwise comparison of the costs incurred by two algorithms on sets of request sequences of the same size. Coupled with a well-established model of locality of reference due to Albers et al. [2005], we show that Least-Recently-Used and Move-to-Front are the unique optimal algorithms for paging and list update, respectively. Prior to this work, only measures based on average-cost analysis have separated LRU and MTF from all other algorithms. Given that bijective analysis is a fairly stringent measure (and also subsumes average-cost analysis), we prove that in a strong sense LRU and MTF stand out as the best (deterministic) algorithms.\n          <\/jats:p>","DOI":"10.1145\/2450142.2450143","type":"journal-article","created":{"date-parts":[[2013,5,1]],"date-time":"2013-05-01T19:47:09Z","timestamp":1367437629000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Paging and list update under bijective analysis"],"prefix":"10.1145","volume":"60","author":[{"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[{"name":"CNRS and Universit\u00e9 Pierre et Marie Curie, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Ishikawa, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.08.002"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009217"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 229--237","author":"Angelopoulos S.","key":"e_1_2_1_4_1","unstructured":"Angelopoulos , S. , Dorrigiv , R. , and L\u00f3pez-Ortiz , A . 2007. On the separation and equivalence of paging strategies . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 229--237 . Angelopoulos, S., Dorrigiv, R., and L\u00f3pez-Ortiz, A. 2007. On the separation and equivalence of paging strategies. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 229--237."},{"volume-title":"Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN). 399--410","author":"Angelopoulos S.","key":"e_1_2_1_5_1","unstructured":"Angelopoulos , S. , Dorrigiv , R. , and L\u00f3pez-Ortiz , A . 2008. List update with locality of reference . In Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN). 399--410 . Angelopoulos, S., Dorrigiv, R., and L\u00f3pez-Ortiz, A. 2008. List update with locality of reference. In Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN). 399--410."},{"volume-title":"Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1137--1145","author":"Angelopoulos S.","key":"e_1_2_1_6_1","unstructured":"Angelopoulos , S. and Schweitzer , P . 2009. Paging and list update under bijective analysis . In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1137--1145 . Angelopoulos, S. and Schweitzer, P. 2009. Paging and list update under bijective analysis. In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1137--1145."},{"volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA). 53--62","author":"Bachrach R.","key":"e_1_2_1_7_1","unstructured":"Bachrach , R. and El-Yaniv , R . 1997. Online list accessing algorithms and their applications: Recent empirical evidence . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA). 53--62 . Bachrach, R. and El-Yaniv, R. 1997. Online list accessing algorithms and their applications: Recent empirical evidence. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Mathematics (SODA). 53--62."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0069-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_11"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294264"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341.3349"},{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","key":"e_1_2_1_12_1","unstructured":"Borodin , A. and El-Yaniv , R. 1998. Online Computation and Competitive Analysis . Cambridge University Press . Borodin, A. and El-Yaniv, R. 1998. Online Computation and Competitive Analysis. Cambridge University Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1021"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11970125_8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.001"},{"key":"e_1_2_1_16_1","unstructured":"Boyar J. Irani S. and Larsen K. S. 2008. A comparison of performance measures for online algorithms. arXiv.org number 0806.0983v1.  Boyar J. Irani S. and Larsen K. S. 2008. A comparison of performance measures for online algorithms. arXiv.org number 0806.0983v1."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361786"},{"key":"e_1_2_1_18_1","unstructured":"Burrows M. and Wheeler D. J. 1994. A block-sorting lossless data compression algorithm. Tech. rep. 124 DEC SRC.  Burrows M. and Wheeler D. J. 1994. A block-sorting lossless data compression algorithm. Tech. rep. 124 DEC SRC."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009255"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/363095.363141"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1086649.1086670"},{"key":"e_1_2_1_22_1","volume-title":"Lecture Notes in Computer Science","volume":"1442","author":"Fiat A.","unstructured":"Fiat , A. and Woeginger , G. J . 1998. Online Algorithms\u2014The State of the Art . Lecture Notes in Computer Science , vol. 1442 , Springer-Verlag. Fiat, A. and Woeginger, G. J. 1998. Online Algorithms\u2014The State of the Art. Lecture Notes in Computer Science, vol. 1442, Springer-Verlag."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/5505.5507"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_44"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780441_26"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762111"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268042"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA). 359--364","author":"Kenyon C.","year":"1996","unstructured":"Kenyon , C. 1996 . Best-fit bin-packing with random order . In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA). 359--364 . Kenyon, C. 1996. Best-fit bin-packing with random order. In Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA). 359--364."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796299540"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00264-3"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/647910.740474"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132587"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/359997.360000"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/646341.686576"},{"key":"e_1_2_1_35_1","unstructured":"Silberschatz A. Galvin P. B. and Gagne G. 2001. Operating System Concepts. Wiley & New York.   Silberschatz A. Galvin P. B. and Gagne G. 2001. Operating System Concepts. Wiley & New York."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009192"},{"key":"e_1_2_1_38_1","unstructured":"Witten I. H. and Bell T. The Calgary\/Canterbury text compression corpus. ftp:\/\/ftp.cpsc.ucalgary.ca\/pub\/projects\/.  Witten I. H. and Bell T. The Calgary\/Canterbury text compression corpus. ftp:\/\/ftp.cpsc.ucalgary.ca\/pub\/projects\/."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189992"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 420--425","author":"Young N. E.","year":"1998","unstructured":"Young , N. E. 1998 . Bounding the diffuse adversary . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 420--425 . Young, N. E. 1998. Bounding the diffuse adversary. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 420--425."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1099"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0124-5"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450142.2450143","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2450142.2450143","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:49Z","timestamp":1750234729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450142.2450143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.1145\/2450142.2450143"],"URL":"https:\/\/doi.org\/10.1145\/2450142.2450143","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2013,4]]},"assertion":[{"value":"2009-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}