{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:19Z","timestamp":1740109279967,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,8,19]],"date-time":"2016-08-19T00:00:00Z","timestamp":1471564800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky (CZ)","award":["P202\/12\/G061","14-10003S"],"award-info":[{"award-number":["P202\/12\/G061","14-10003S"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00453-016-0185-0","type":"journal-article","created":{"date-parts":[[2016,8,19]],"date-time":"2016-08-19T09:25:27Z","timestamp":1471598727000},"page":"319-339","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["General Caching Is Hard: Even with Small Pages"],"prefix":"10.1007","volume":"79","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3020-6443","authenticated-orcid":false,"given":"Luk\u00e1\u0161","family":"Folwarczn\u00fd","sequence":"first","affiliation":[]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,19]]},"reference":[{"issue":"1\u20132","key":"185_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. Theor. Comput. Sci. 234(1\u20132), 203\u2013218 (2000). doi:\n                        10.1016\/S0304-3975(98)00116-9\n                        \n                    . (A\u00a0preliminary version appeared at ESA\u00a01996)","journal-title":"Theor. Comput. Sci."},{"key":"185_CR2","doi-asserted-by":"publisher","unstructured":"Adamaszek, A., Czumaj, A., Englert, M., R\u00e4cke, H.: An O(log k)-competitive algorithm for generalized caching. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1681\u20131689 (2012). doi:\n                        10.1137\/1.9781611973099","DOI":"10.1137\/1.9781611973099"},{"key":"185_CR3","unstructured":"Albers, S., Arora, S., Khanna, S.: Page replacement for general caching problems. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 31\u201340 (1999). \n                        http:\/\/dl.acm.org\/citation.cfm?id=314500.314528"},{"key":"185_CR4","doi-asserted-by":"publisher","unstructured":"Anagnostopoulos, A., Grandoni, F., Leonardi, S., Wiese, A.: A mazing \n                        $$2+\\epsilon $$\n                        \n                            \n                                            \n                                \n                                    2\n                                    +\n                                    \u03f5\n                                \n                            \n                        \n                     approximation for unsplittable flow on a path. In: Chekuri, C. (ed.) Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pp. 26\u201341. SIAM (2014). doi:\n                        10.1137\/1.9781611973402.3","DOI":"10.1137\/1.9781611973402.3"},{"issue":"2","key":"185_CR5","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1137\/090779000","volume":"41","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Buchbinder, N., Naor, J.: Randomized competitive algorithms for generalized caching. SIAM J. Comput. 41(2), 391\u2013414 (2012). doi:\n                        10.1137\/090779000\n                        \n                    . (A\u00a0preliminary version appeared at STOC\u00a02008)","journal-title":"SIAM J. Comput."},{"key":"185_CR6","doi-asserted-by":"publisher","unstructured":"Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-PTAS for unsplittable flow on line graphs. In: Kleinberg, J.M. (ed.) Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 721\u2013729. ACM (2006). doi:\n                        10.1145\/1132516.1132617","DOI":"10.1145\/1132516.1132617"},{"issue":"5","key":"185_CR7","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069\u20131090 (2001). doi:\n                        10.1145\/502102.502107\n                        \n                    . (A\u00a0preliminary version appeared at STOC\u00a02000)","journal-title":"J. ACM"},{"key":"185_CR8","doi-asserted-by":"publisher","unstructured":"Batra, J., Garg, N., Kumar, A., M\u00f6mke, T., Wiese, A.: New approximation schemes for unsplittable flow on a path. In: Indyk, P. (ed.) Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 47\u201358. SIAM (2015). doi:\n                        10.1137\/1.9781611973730.5","DOI":"10.1137\/1.9781611973730.5"},{"issue":"2","key":"185_CR9","doi-asserted-by":"publisher","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 a virtual-storage computer. IBM Syst. J. 5(2), 78\u2013101 (1966). doi:\n                        10.1147\/sj.52.0078","journal-title":"IBM Syst. J."},{"issue":"2","key":"185_CR10","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1137\/120868360","volume":"43","author":"PS Bonsma","year":"2014","unstructured":"Bonsma, P.S., Schulz, J., Wiese, A.: A constant-factor approximation algorithm for unsplittable flow on paths. SIAM J. Comput. 43(2), 767\u2013799 (2014). doi:\n                        10.1137\/120868360","journal-title":"SIAM J. Comput."},{"key":"185_CR11","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)"},{"issue":"1","key":"185_CR12","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). doi:\n                        10.1007\/s00224-012-9427-y\n                        \n                    . (A\u00a0preliminary version appeared at WAOA\u00a02011)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"185_CR13","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/0404017","volume":"4","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Karloff, H.J., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discrete Math. 4(2), 172\u2013181 (1991). doi:\n                        10.1137\/0404017\n                        \n                    . (A\u00a0preliminary version appeared at SODA\u00a01990)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"185_CR14","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0020-0190(97)00099-9","volume":"63","author":"M Chrobak","year":"1997","unstructured":"Chrobak, M., Larmore, L.L., Lund, C., Reingold, N.: A better lower bound on the competitive ratio of the randomized 2-server problem. Inf. Process. Lett. 63(2), 79\u201383 (1997). doi:\n                        10.1016\/S0020-0190(97)00099-9","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"185_CR15","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1007\/s00453-011-9502-9","volume":"63","author":"M Chrobak","year":"2012","unstructured":"Chrobak, M., Woeginger, G.J., Makino, K., Xu, H.: Caching is hard\u2013even in the fault model. Algorithmica 63(4), 781\u2013794 (2012). doi:\n                        10.1007\/s00453-011-9502-9\n                        \n                    . (A\u00a0preliminary version appeared at ESA\u00a02010)","journal-title":"Algorithmica"},{"issue":"49","key":"185_CR16","doi-asserted-by":"publisher","first-page":"4217","DOI":"10.1016\/j.tcs.2010.08.028","volume":"411","author":"A Darmann","year":"2010","unstructured":"Darmann, A., Pferschy, U., Schauer, J.: Resource allocation with time intervals. Theor. Comput. Sci. 411(49), 4217\u20134234 (2010). doi:\n                        10.1016\/j.tcs.2010.08.028","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"185_CR17","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. J. Algorithms 12(4), 685\u2013699 (1991). doi:\n                        10.1016\/0196-6774(91)90041-V\n                        \n                    . (A\u00a0preliminary version appeared in\u00a01988)","journal-title":"J. Algorithms"},{"key":"185_CR18","doi-asserted-by":"publisher","unstructured":"Folwarczn\u00fd, L., Sgall, J.: General caching is hard: Even with small pages. In: Elbassioni, K.M., Makino, K. (eds.) Algorithms and Computation\u201426th International Symposium, ISAAC 2015, Nagoya, Japan, December 9\u201311, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9472, pp. 116\u2013126. Springer (2015). doi:\n                        10.1007\/978-3-662-48971-0_11","DOI":"10.1007\/978-3-662-48971-0_11"},{"issue":"3","key":"185_CR19","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/s00453-001-0125-4","volume":"33","author":"S Irani","year":"2002","unstructured":"Irani, S.: Page replacement with multi-size pages and applications to web caching. Algorithmica 33(3), 384\u2013409 (2002). doi:\n                        10.1007\/s00453-001-0125-4\n                        \n                    . (A\u00a0preliminary version appeared at STOC\u00a01997)","journal-title":"Algorithmica"},{"issue":"6","key":"185_CR20","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"LA McGeoch","year":"1991","unstructured":"McGeoch, L.A., Sleator, D.D.: A strongly competitive randomized paging algorithm. Algorithmica 6(6), 816\u2013825 (1991). doi:\n                        10.1007\/BF01759073\n                        \n                    . (A\u00a0preliminary version appeared in\u00a01989)","journal-title":"Algorithmica"},{"issue":"3","key":"185_CR21","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). doi:\n                        10.1007\/s00453-001-0124-5\n                        \n                    . (A\u00a0preliminary version appeared at SODA 1998)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0185-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0185-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0185-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0185-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T14:34:35Z","timestamp":1501511675000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0185-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,19]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["185"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0185-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,8,19]]}}}