{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:57:17Z","timestamp":1725555437929},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642124495"},{"type":"electronic","value":"9783642124501"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12450-1_10","type":"book-chapter","created":{"date-parts":[[2010,5,5]],"date-time":"2010-05-05T19:01:49Z","timestamp":1273086109000},"page":"104-115","source":"Crossref","is-referenced-by-count":12,"title":["Parameterized Analysis of Paging and List Update Algorithms"],"prefix":"10.1007","author":[{"given":"Reza","family":"Dorrigiv","sequence":"first","affiliation":[]},{"given":"Martin R.","family":"Ehmsen","sequence":"additional","affiliation":[]},{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"10_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 Journal on Computing\u00a027(3), 682\u2013693 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"10_CR2","first-page":"145","volume":"70","author":"S. Albers","year":"2005","unstructured":"Albers, S., Favrholdt, L.M., Giel, O.: On paging with locality of reference. JCSS\u00a070(2), 145\u2013175 (2005)","journal-title":"JCSS"},{"key":"10_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-540-70575-8_9","volume-title":"Automata, Languages and Programming","author":"S. Albers","year":"2008","unstructured":"Albers, S., Lauer, S.: On list update with locality of reference. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 96\u2013107. Springer, Heidelberg (2008)"},{"key":"10_CR4","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-Ortiz, A.: On the separation and equivalence of paging strategies. In: Proc. SODA, pp. 229\u2013237 (2007)"},{"key":"10_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-540-78773-0_35","volume-title":"LATIN 2008: Theoretical Informatics","author":"S. Angelopoulos","year":"2008","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-Ortiz, A.: List update with locality of reference. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 399\u2013410. Springer, Heidelberg (2008)"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., Schweitzer, P.: Paging and list update under bijective analysis. In: Proc. SODA, pp. 1136\u20131145 (2009)","DOI":"10.1137\/1.9781611973068.123"},{"key":"10_CR7","unstructured":"Bachrach, R., El-Yaniv, R.: Online list accessing algorithms and their applications: Recent empirical evidence. In: Proc. SODA, pp. 53\u201362 (1997)"},{"key":"10_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/978-3-540-30140-0_11","volume-title":"Algorithms \u2013 ESA 2004","author":"L. Becchetti","year":"2004","unstructured":"Becchetti, L.: Modeling locality: A probabilistic analysis of LRU and FWF. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 98\u2013109. Springer, Heidelberg (2004)"},{"key":"10_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\u00a011, 73\u201391 (1994)","journal-title":"Algorithmica"},{"key":"10_CR10","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":"10_CR11","first-page":"244","volume":"50","author":"A. Borodin","year":"1995","unstructured":"Borodin, A., Irani, S., Raghavan, P., Schieber, B.: Competitive paging with locality of reference. JCSS\u00a050, 244\u2013258 (1995)","journal-title":"JCSS"},{"key":"10_CR12","unstructured":"Bose, P., Dou\u00efeb, K., Langerman, S.: Dynamic optimality for skip lists and B-trees. In: Proc. SODA, pp. 1106\u20131114 (2008)"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/11970125_8","volume-title":"Approximation and Online Algorithms","author":"J. Boyar","year":"2007","unstructured":"Boyar, J., Ehmsen, M.R., Larsen, K.S.: Theoretical evidence for the superiority of LRU-2 over LRU for the paging problem. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol.\u00a04368, pp. 95\u2013107. Springer, Heidelberg (2007)"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Boyar, J., Favrholdt, L.M.: The relative worst order ratio for on-line algorithms. In: Proc. Italian Conf. on Algorithms and Complexity (2003)","DOI":"10.1007\/3-540-44849-7_13"},{"issue":"2","key":"10_CR15","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\u00a023(2), 180\u2013185 (1999)","journal-title":"Algorithmica"},{"issue":"5","key":"10_CR16","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1145\/363095.363141","volume":"11","author":"P.J. Denning","year":"1968","unstructured":"Denning, P.J.: The working set model for program behaviour. CACM\u00a011(5), 323\u2013333 (1968)","journal-title":"CACM"},{"issue":"1","key":"10_CR17","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1109\/TSE.1980.230464","volume":"SE-6","author":"P.J. Denning","year":"1980","unstructured":"Denning, P.J.: Working sets past and present. IEEE Transactions on Software Engineering\u00a0SE-6(1), 64\u201384 (1980)","journal-title":"IEEE Transactions on Software Engineering"},{"issue":"7","key":"10_CR18","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1070838.1070856","volume":"48","author":"P.J. Denning","year":"2005","unstructured":"Denning, P.J.: The locality principle. CACM\u00a048(7), 19\u201324 (2005)","journal-title":"CACM"},{"issue":"3","key":"10_CR19","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/1086649.1086670","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\u00a036(3), 67\u201381 (2005)","journal-title":"SIGACT News"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/0196-6774(91)90041-V","volume":"12","author":"A. Fiat","year":"1991","unstructured":"Fiat, A., Karp, R.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E.: Competitive paging algorithms. Journal of Algorithms\u00a012, 685\u2013699 (1991)","journal-title":"Journal of Algorithms"},{"key":"10_CR21","unstructured":"Fiat, A., Rosen, Z.: Experimental studies of access graph based heuristics: Beating the LRU standard? In: Proc. SODA, pp. 63\u201372 (1997)"},{"issue":"3","key":"10_CR22","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1145\/5505.5507","volume":"17","author":"J.H. Hester","year":"1985","unstructured":"Hester, J.H., Hirschberg, D.S.: Self-organizing linear search. ACM Computing Surveys\u00a017(3), 295 (1985)","journal-title":"ACM Computing Surveys"},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-44985-X_5","volume-title":"Algorithm Theory - SWAT 2000","author":"J. Iacono","year":"2000","unstructured":"Iacono, J.: Improved upper bounds for pairing heaps. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 32\u201345. Springer, Heidelberg (2000)"},{"key":"10_CR24","unstructured":"Iacono, J.: Alternatives to splay trees with O(log n) worst-case access times. In: Proc. SODA, pp. 516\u2013522 (2001)"},{"key":"10_CR25","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 Journal on Computing\u00a025, 477\u2013497 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"10_CR26","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1137\/S0097539794268042","volume":"30","author":"A.R. Karlin","year":"2000","unstructured":"Karlin, A.R., Phillips, S.J., Raghavan, P.: Markov paging. SIAM Journal on Computing\u00a030(3), 906\u2013922 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR27","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: Proc. SODA, pp. 359\u2013364 (1996)"},{"key":"10_CR28","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 Journal on Computing\u00a030, 300\u2013317 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR29","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: Proc. ACM SIGMOD Conf., pp. 297\u2013306 (1993)","DOI":"10.1145\/170035.170081"},{"key":"10_CR30","unstructured":"Reingold, N., Westbrook, J.: Randomized algorithms for the list update problem. Technical Report YALEU\/DCS\/TR-804, Yale University (June 1990)"},{"key":"10_CR31","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\u00a011, 15\u201332 (1994)","journal-title":"Algorithmica"},{"key":"10_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-49381-6_12","volume-title":"Algorithms and Computation","author":"F. Schulz","year":"1998","unstructured":"Schulz, F.: Two new families of list update algorithms. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol.\u00a01533, pp. 99\u2013108. Springer, Heidelberg (1998)"},{"key":"10_CR33","volume-title":"Operating System Concepts","author":"A. Silberschatz","year":"2002","unstructured":"Silberschatz, A., Galvin, P.B., Gagne, G.: Operating System Concepts. John Wiley & Sons, Chichester (2002)"},{"key":"10_CR34","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. CACM\u00a028, 202\u2013208 (1985)","journal-title":"CACM"},{"issue":"3","key":"10_CR35","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. JACM\u00a032(3), 652\u2013686 (1985)","journal-title":"JACM"},{"key":"10_CR36","unstructured":"N.M.S. University: Homepage of new mexico state university tracebase (online), \n                    \n                      http:\/\/tracebase.nmsu.edu\/tracebase.html"},{"issue":"6","key":"10_CR37","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"N.E. Young","year":"1994","unstructured":"Young, N.E.: The k-server dual and loose competitiveness for paging. Algorithmica\u00a011(6), 525\u2013541 (1994)","journal-title":"Algorithmica"},{"issue":"1","key":"10_CR38","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1006\/jagm.2000.1099","volume":"37","author":"N.E. Young","year":"2000","unstructured":"Young, N.E.: On-line paging against adversarially biased random inputs. Journal of Algorithms\u00a037(1), 218\u2013235 (2000)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"10_CR39","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s00453-001-0124-5","volume":"33","author":"N.E. Young","year":"2002","unstructured":"Young, N.E.: Online file caching. Algorithmica\u00a033(3), 371\u2013383 (2002)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12450-1_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T11:41:43Z","timestamp":1619782903000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12450-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642124495","9783642124501"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12450-1_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}