{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T21:09:22Z","timestamp":1778792962067,"version":"3.51.4"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s00453-011-9502-9","type":"journal-article","created":{"date-parts":[[2011,3,9]],"date-time":"2011-03-09T21:11:28Z","timestamp":1299705088000},"page":"781-794","source":"Crossref","is-referenced-by-count":27,"title":["Caching Is Hard\u2014Even in the Fault Model"],"prefix":"10.1007","volume":"63","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haifeng","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,3,10]]},"reference":[{"key":"9502_CR1","first-page":"31","volume-title":"Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA\u201999)","author":"S. Albers","year":"1999","unstructured":"Albers, S., Arora, S., Khanna, S.: Page replacement for general caching problems. In: Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA\u201999), pp. 31\u201340 (1999)"},{"key":"9502_CR2","first-page":"721","volume-title":"Proc. 38th Annual ACM Symposium on Theory of Computing (STOC\u201906)","author":"N. Bansal","year":"2006","unstructured":"Bansal, N., Chakrabarti, A., Epstein, A., Schieber, B.: A quasi-PTAS for unsplittable flow on line graphs. In: Proc. 38th Annual ACM Symposium on Theory of Computing (STOC\u201906), pp. 721\u2013729 (2006)"},{"key":"9502_CR3","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1145\/1374376.1374412","volume-title":"Proc. 40th Annual ACM Symposium on Theory of Computing (STOC\u201908)","author":"N. Bansal","year":"2008","unstructured":"Bansal, N., Buchbinder, N., Naor, J.: Randomized competitive algorithms for generalized caching. In: Proc. 40th Annual ACM Symposium on Theory of Computing (STOC\u201908), pp. 235\u2013244 (2008)"},{"key":"9502_CR4","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1137\/1.9781611973068.77","volume-title":"Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909)","author":"N. Bansal","year":"2009","unstructured":"Bansal, N., Friggstad, Z., Khandekar, R., Salavatipour, M.R.: A logarithmic approximation for unsplittable flow on line graphs. In: Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909), pp. 702\u2013709 (2009)"},{"key":"9502_CR5","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A. Bar-Noy","year":"2000","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, 1069\u20131090 (2000)","journal-title":"J. ACM"},{"key":"9502_CR6","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"L.A. Belady","year":"1966","unstructured":"Belady, L.A.: A study of replacement algorithms for virtual-storage computer. IBM Syst. J. 5, 78\u2013101 (1966)","journal-title":"IBM Syst. J."},{"key":"9502_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, Cambridge (1998)"},{"key":"9502_CR8","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1109\/TC.2004.1255792","volume":"53","author":"M. Brehob","year":"2004","unstructured":"Brehob, M., Wagner, S., Torng, E., Enbody, R.: Optimal replacement is NP-hard for non-standard caches. IEEE Trans. Comput. 53, 73\u201376 (2004)","journal-title":"IEEE Trans. Comput."},{"key":"9502_CR9","first-page":"193","volume-title":"Proc. USENIX Symposium on Internet Technologies and Systems","author":"P. Cao","year":"1997","unstructured":"Cao, P., Irani, S.: Cost-aware www proxy caching algorithms. In: Proc. USENIX Symposium on Internet Technologies and Systems, pp. 193\u2013206 (1997)"},{"key":"9502_CR10","doi-asserted-by":"crossref","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, 172\u2013181 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"9502_CR11","unstructured":"Fiat, A.: Unpublished manuscript, 1997"},{"key":"9502_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of ${\\mathbb {NP}}$ -Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of ${\\mathbb {NP}}$ -Completeness. Freeman, San Francisco (1979)"},{"key":"9502_CR13","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1007\/s00453-001-0125-4","volume":"33","author":"S. Irani","year":"1997","unstructured":"Irani, S.: Page replacement with multi-size pages and applications to web caching. Algorithmica 33, 384\u2013409 (1997)","journal-title":"Algorithmica"},{"key":"9502_CR14","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/s00453-001-0124-5","volume":"33","author":"N.E. Young","year":"2002","unstructured":"Young, N.E.: On-line file caching. Algorithmica 33, 371\u2013383 (2002)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00453-011-9502-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,20]],"date-time":"2021-11-20T05:21:12Z","timestamp":1637385672000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9502-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,10]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["9502"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9502-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,10]]}}}