{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T01:53:39Z","timestamp":1725846819138},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662491911"},{"type":"electronic","value":"9783662491928"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49192-8_22","type":"book-chapter","created":{"date-parts":[[2016,1,7]],"date-time":"2016-01-07T10:47:27Z","timestamp":1452163647000},"page":"265-276","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Paging Against a Probabilistic Adversary"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Dobrev","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Dennis","family":"Komm","sequence":"additional","affiliation":[]},{"given":"Richard","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[]},{"given":"Rastislav","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[]},{"given":"Tobias","family":"M\u00f6mke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,8]]},"reference":[{"issue":"1","key":"22_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-003-0436-0","volume":"97","author":"S Albers","year":"2003","unstructured":"Albers, S.: Online algorithms: a survey. Math. Program. 97(1), 3\u201326 (2003)","journal-title":"Math. Program."},{"issue":"2","key":"22_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"LA B\u00e9l\u00e1dy","year":"1966","unstructured":"B\u00e9l\u00e1dy, L.A.: A study of replacement algorithms for virtual-storage computer. IBM Syst. J. 5(2), 78\u2013101 (1966)","journal-title":"IBM Syst. J."},{"issue":"1","key":"22_CR3","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":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-642-10631-6_35","volume-title":"Algorithms and Computation","author":"H-J B\u00f6ckenhauer","year":"2009","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: On the advice complexity of online problems. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 331\u2013340. Springer, Heidelberg (2009)"},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-22006-7_18","volume-title":"Automata, Languages and Programming","author":"H-J B\u00f6ckenhauer","year":"2011","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R.: On the advice complexity of the \n                      \n                        \n                      \n                      $$k$$\n                    -server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) Automata, Languages and Programming. LNCS, vol. 6755, pp. 207\u2013218. Springer, Heidelberg (2011)"},{"key":"22_CR6","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, New York (1998)"},{"issue":"2","key":"22_CR7","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":"1","key":"22_CR8","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."},{"key":"22_CR9","unstructured":"Chou, A., Cooperstock, J., El-Yaniv, R., Klugerman, M., Leighton, T.: The statistical adversary allows optimal money-making trading strategies. In: Proceeding of SODA 1995, pp. 467\u2013476. Society for Industrial and Applied Mathematics (1995)"},{"key":"22_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-540-77566-9_21","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"S Dobrev","year":"2008","unstructured":"Dobrev, S., Kr\u00e1lovi\u010d, R., Pardubsk\u00e1, D.: How much information about the future is needed? In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol. 4910, pp. 247\u2013258. Springer, Heidelberg (2008)"},{"issue":"24","key":"22_CR11","doi-asserted-by":"publisher","first-page":"2642","DOI":"10.1016\/j.tcs.2010.08.007","volume":"412","author":"Y Emek","year":"2011","unstructured":"Emek, Y., Fraigniaud, P., Korman, A., Ros\u00e9n, A.: Online computation with advice. Theor. Comput. Sci. 412(24), 2642\u20132656 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR12","unstructured":"Harel, D., Feldman, Y.: Algorithmics: The Spirit of Computing. Addison-Wesley, 3rd edn (2004)"},{"issue":"1","key":"22_CR13","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321796.321800","volume":"21","author":"PA Franaszek","year":"1974","unstructured":"Franaszek, P.A., Wagner, T.J.: Some distribution-free aspects of paging algorithm performance. J. ACM 21(1), 31\u201339 (1974)","journal-title":"J. ACM"},{"key":"22_CR14","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)"},{"key":"22_CR15","unstructured":"Irani, S., Karlin, A.R.: On online computation. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-hard Problems, pp. 521\u2013564. PWS Publishing Company (1997)"},{"issue":"2","key":"22_CR16","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1051\/ita\/2011105","volume":"45","author":"D Komm","year":"2011","unstructured":"Komm, D., Kr\u00e1lovi\u010d, R.: Advice complexity and barely random algorithms. Theor. Inf. Appl. (RAIRO) 45(2), 249\u2013267 (2011)","journal-title":"Theor. Inf. Appl. (RAIRO)"},{"issue":"1","key":"22_CR17","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","key":"22_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1186810.1186817","volume":"3","author":"G Pandurangan","year":"2007","unstructured":"Pandurangan, G., Upfal, E.: Entropy-based bounds for online algorithms. ACM Trans. Algorithms 3(1), 1\u201319 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"22_CR19","first-page":"79","volume":"7","author":"P Raghavan","year":"1991","unstructured":"Raghavan, P.: A statistical adversary for on-line algorithms. DIMACS 7, 79\u201383 (1991)","journal-title":"DIMACS"},{"key":"22_CR20","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1137\/0201016","volume":"1","author":"GS Shedler","year":"1972","unstructured":"Shedler, G.S., Tung, C.: Locality in page reference strings. SIAM J. Comput. 1, 218\u2013241 (1972)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"22_CR21","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. Communications of the ACM 28(2), 202\u2013208 (1985)","journal-title":"Communications of the ACM"},{"key":"22_CR22","series-title":"Lecture Notes in Computer Science","volume-title":"Online Algorithms, The State of the Art","year":"1998","unstructured":"Fiat, A. (ed.): Online Algorithms 1996. LNCS, vol. 1442. Springer, Heidelberg (1998)"},{"key":"22_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BFb0029578","volume-title":"Online Algorithms, The State of the Art","author":"A Fiat","year":"1998","unstructured":"Fiat, A., Woeginger, G.J.: Competitive odds and ends. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms 1996. LNCS, vol. 1442, pp. 385\u2013394. Springer, Heidelberg (1998)"},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In: Proceeding of FOCS 1977, pp. 222\u2013227. IEEE Computer Society (1977)","DOI":"10.1109\/SFCS.1977.24"},{"key":"22_CR25","unstructured":"Young, N.E.: Bounding the diffuse adversary. In: Proceeding of SODA 1998, pp. 420\u2013425. Society for Industrial and Applied Mathematics (1998)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2016: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49192-8_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T05:09:23Z","timestamp":1559365763000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49192-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662491911","9783662491928"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49192-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}