{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T09:31:19Z","timestamp":1770283879409,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,10,13]],"date-time":"2017-10-13T00:00:00Z","timestamp":1507852800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SFB\/TR 14 AVACS"],"award-info":[{"award-number":["SFB\/TR 14 AVACS"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["PEP: Precise and Efficient Prediction of Good Worst-case Performance for Contemporary and Future Architectures"],"award-info":[{"award-number":["PEP: Precise and Efficient Prediction of Good Worst-case Performance for Contemporary and Future Architectures"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00224-017-9813-6","type":"journal-article","created":{"date-parts":[[2017,10,12]],"date-time":"2017-10-12T22:37:41Z","timestamp":1507847861000},"page":"366-418","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Smoothness of Paging Algorithms"],"prefix":"10.1007","volume":"62","author":[{"given":"Jan","family":"Reineke","sequence":"first","affiliation":[]},{"given":"Alejandro","family":"Salinger","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,10,13]]},"reference":[{"issue":"1-2","key":"9813_CR1","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0304-3975(98)00116-9","volume":"234","author":"D Achlioptas","year":"2000","unstructured":"Achlioptas, D., Chrobak, M., Noga, J.: Competitive analysis of randomized paging algorithms. Theoretical Comput. Sci. 234 (1-2), 203\u2013218 (2000). \n                        https:\/\/doi.org\/10.1016\/S0304-3975(98)00116-9\n                        \n                    . \n                        http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397598001169","journal-title":"Theoretical Comput. Sci."},{"issue":"1","key":"9813_CR2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1145\/321623.321632","volume":"18","author":"A Aho","year":"1971","unstructured":"Aho, A., Denning, P., Ullman, J.: Principles of optimal page replacement. J. ACM 18(1), 80\u201393 (1971)","journal-title":"J. ACM"},{"issue":"4","key":"9813_CR3","doi-asserted-by":"publisher","first-page":"82:1","DOI":"10.1145\/2560033","volume":"13","author":"P Axer","year":"2014","unstructured":"Axer, P., et al.: Building timing predictable embedded systems. ACM Trans. Embed. Comput. Syst. 13(4), 82:1\u20138:372 (2014). \n                        https:\/\/doi.org\/10.1145\/2560033","journal-title":"ACM Trans. Embed. Comput. Syst."},{"issue":"1","key":"9813_CR4","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1287\/moor.1050.0170","volume":"31","author":"L Becchetti","year":"2006","unstructured":"Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Sch\u00e4fer, G., Vredeveld, T.: Average-case and smoothed competitive analysis of the multilevel feedback algorithm. Math. Oper. Res. 31(1), 85\u2013108 (2006). \n                        https:\/\/doi.org\/10.1287\/moor.1050.0170","journal-title":"Math. Oper. Res."},{"key":"9813_CR5","doi-asserted-by":"publisher","unstructured":"Beckmann, N., Sanchez, D.: Talus: a Simple Way to Remove Cliffs in Cache Performance. In: 21St IEEE International Symposium on High Performance Computer Architecture, HPCA 2015, Burlingame, CA, USA, February 7-11, 2015, pp. 64\u201375 (2015). \n                        https:\/\/doi.org\/10.1109\/HPCA.2015.7056022","DOI":"10.1109\/HPCA.2015.7056022"},{"issue":"2","key":"9813_CR6","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"LA Belady","year":"1966","unstructured":"Belady, L.A.: A study of replacement algorithms for virtual-storage computer. IBM Syst. J. 5(2), 78\u2013101 (1966)","journal-title":"IBM Syst. J."},{"key":"9813_CR7","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, New York (1998)"},{"issue":"1","key":"9813_CR8","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s00224-012-9427-y","volume":"56","author":"GS Brodal","year":"2015","unstructured":"Brodal, G.S., Moruz, G., Negoescu, A.: Onlinemin: a fast strongly competitive randomized paging algorithm. Theory Comput. Syst. 56(1), 22\u201340 (2015). \n                        https:\/\/doi.org\/10.1007\/s00224-012-9427-y","journal-title":"Theory Comput. Syst."},{"issue":"2s","key":"9813_CR9","doi-asserted-by":"publisher","first-page":"94:1","DOI":"10.1145\/2465787.2465796","volume":"12","author":"FJ Cazorla","year":"2013","unstructured":"Cazorla, F.J., et al.: PROARTIS: Probabilistically analyzable real-time systems. ACM Trans. Embed. Comput. Syst. 12(2s), 94:1\u201394:26 (2013). \n                        https:\/\/doi.org\/10.1145\/2465787.2465796","journal-title":"ACM Trans. Embed. Comput. Syst."},{"issue":"8","key":"9813_CR10","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/2240236.2240262","volume":"55","author":"S Chaudhuri","year":"2012","unstructured":"Chaudhuri, S., Gulwani, S., Lublinerman, R.: Continuity and robustness of programs. Commun. ACM 55(8), 107\u2013115 (2012). \n                        https:\/\/doi.org\/10.1145\/2240236.2240262","journal-title":"Commun. ACM"},{"issue":"1","key":"9813_CR11","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/2756550","volume":"18","author":"G Doychev","year":"2015","unstructured":"Doychev, G., et al.: CacheAudit: A tool for the static analysis of cache side channels. ACM Trans. Inf. Syst. Secur 18(1), 4:1\u20134:32 (2015). \n                        https:\/\/doi.org\/10.1145\/2756550","journal-title":"ACM Trans. Inf. Syst. Secur"},{"key":"9813_CR12","doi-asserted-by":"publisher","unstructured":"Doyen, L., Henzinger, T., Legay, A., Nickovic, D.: Robustness of Sequential Circuits. In: ACSD \u201910, pp 77\u201384 (2010). \n                        https:\/\/doi.org\/10.1109\/ACSD.2010.26","DOI":"10.1109\/ACSD.2010.26"},{"key":"9813_CR13","doi-asserted-by":"publisher","unstructured":"Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP \u201906, Part II, LNCS, vol. 4052, pp 1\u201312. Springer (2006). \n                        https:\/\/doi.org\/10.1007\/11787006_1","DOI":"10.1007\/11787006_1"},{"issue":"4","key":"9813_CR14","doi-asserted-by":"crossref","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. J. Algorithms 12(4), 685\u2013699 (1991)","journal-title":"J. Algorithms"},{"key":"9813_CR15","volume-title":"Automata studies, chap. Representation of events in nerve nets and finite automata","author":"S Kleene","year":"1956","unstructured":"Kleene, S.: Automata studies, chap. Representation of events in nerve nets and finite automata. Princeton University Press, Princeton (1956)"},{"key":"9813_CR16","unstructured":"Komm, D., Kr\u00e1lovic, R., Kr\u00e1lovic, R., M\u00f6mke, T.: Randomized online algorithms with high probability guarantees. In: STACS \u201914, vol. 25, pp 470\u2013481 (2014)"},{"issue":"1","key":"9813_CR17","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(1), 300\u2013317 (2000). \n                        https:\/\/doi.org\/10.1137\/S0097539796299540","journal-title":"SIAM J. Comput."},{"key":"9813_CR18","unstructured":"Liu, C.L.: Some memory aspects of finite automata. Tech. Rep. 411 Massachusetts Institute of Technology (1963)"},{"issue":"2","key":"9813_CR19","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1147\/sj.92.0078","volume":"9","author":"RL Mattson","year":"1970","unstructured":"Mattson, R.L., Gecsei, J., Slutz, D.R., Traiger, I.L.: Evaluation techniques for storage hierarchies. IBM Syst. J. 9(2), 78\u2013117 (1970)","journal-title":"IBM Syst. J."},{"key":"9813_CR20","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"L McGeoch","year":"1991","unstructured":"McGeoch, L., Sleator, D.: A strongly competitive randomized paging algorithm. Algorithmica 6, 816\u2013825 (1991). \n                        https:\/\/doi.org\/10.1007\/BF01759073","journal-title":"Algorithmica"},{"key":"9813_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, New York (1995)"},{"issue":"3","key":"9813_CR22","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1109\/PGEC.1963.263534","volume":"12","author":"M Perles","year":"1963","unstructured":"Perles, M., Rabin, M., Shamir, E.: The theory of definite automata. IEEE Trans. Electron. Comput. 12(3), 233\u2013243 (1963). \n                        https:\/\/doi.org\/10.1109\/PGEC.1963.263534","journal-title":"IEEE Trans. Electron. Comput."},{"key":"9813_CR23","doi-asserted-by":"publisher","unstructured":"Raghavan, P., Snir, M.: Memory versus randomization in on-line algorithms (Extended Abstract). In: Ausiello, G., Dezani-Ciancaglini, M., Rocca, S.R.D. (eds.) ICALP \u201989, Lecture Notes in Computer Science, vol. 372, pp 687\u2013703. Springer (1989). \n                        https:\/\/doi.org\/10.1007\/BFb0035792","DOI":"10.1007\/BFb0035792"},{"issue":"1s","key":"9813_CR24","doi-asserted-by":"publisher","first-page":"42:1","DOI":"10.1145\/2435227.2435238","volume":"12","author":"J Reineke","year":"2013","unstructured":"Reineke, J., Grund, D.: Sensitivity of cache replacement policies. ACM Trans. Embed. Comput. Syst. 12(1s), 42:1\u201342:18 (2013). \n                        https:\/\/doi.org\/10.1145\/2435227.2435238","journal-title":"ACM Trans. Embed. Comput. Syst."},{"key":"9813_CR25","doi-asserted-by":"publisher","unstructured":"Reineke, J., Salinger, A.: On the smoothness of paging algorithms. In: Sanit\u00e0, L., Skutella, M. (eds.) Approximation and Online Algorithms - 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers, Lecture Notes in Computer Science, vol. 9499, pp 170\u2013182. Springer (2015). \n                        https:\/\/doi.org\/10.1007\/978-3-319-28684-6_15","DOI":"10.1007\/978-3-319-28684-6_15"},{"issue":"2","key":"9813_CR26","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.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"issue":"3","key":"9813_CR27","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). \n                        https:\/\/doi.org\/10.1145\/990308.990310","journal-title":"J. ACM"},{"issue":"3","key":"9813_CR28","doi-asserted-by":"publisher","first-page":"36:1","DOI":"10.1145\/1347375.1347389","volume":"7","author":"R Wilhelm","year":"2008","unstructured":"Wilhelm, R., et al.: The worst-case execution-time problem\u2014overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst. 7(3), 36:1\u201336:53 (2008). \n                        https:\/\/doi.org\/10.1145\/1347375.1347389","journal-title":"ACM Trans. Embed. Comput. Syst."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9813-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9813-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9813-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,5,18]],"date-time":"2018-05-18T11:54:06Z","timestamp":1526644446000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9813-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,13]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["9813"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9813-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,13]]}}}