{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T07:51:24Z","timestamp":1761983484787,"version":"build-2065373602"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662447765"},{"type":"electronic","value":"9783662447772"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44777-2_18","type":"book-chapter","created":{"date-parts":[[2014,8,16]],"date-time":"2014-08-16T10:43:15Z","timestamp":1408185795000},"page":"209-221","source":"Crossref","is-referenced-by-count":7,"title":["Competitive Algorithms for Restricted Caching and Matroid Caching"],"prefix":"10.1007","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[]},{"given":"Shahar","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_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 Computer Science\u00a0234, 203\u2013218 (2000)","journal-title":"Theoretical Computer Science"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Czumaj, A., Englert, M., R\u00e4cke, H.: An o(log k)-competitive algorithm for generalized caching. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1681\u20131689 (2012)","DOI":"10.1137\/1.9781611973099.133"},{"issue":"2","key":"18_CR3","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1137\/060661946","volume":"39","author":"N. Alon","year":"2009","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. SIAM Journal on Computing\u00a039(2), 361\u2013370 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Buchbinder, N., Naor, J.: Towards the randomized k-server conjecture: A primal-dual approach. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 40\u201355 (2010)","DOI":"10.1137\/1.9781611973075.5"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Buchbinder, N., Naor, J.: A primal-dual randomized algorithm for weighted paging. J. ACM\u00a059(4) (2012)","DOI":"10.1145\/2339123.2339126"},{"issue":"2","key":"18_CR6","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.\u00a041(2), 391\u2013414 (2012)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"18_CR7","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1147\/sj.52.0078","volume":"5","author":"L. Belady","year":"1966","unstructured":"Belady, L.: A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal\u00a05(2), 78\u2013101 (1966)","journal-title":"IBM Systems Journal"},{"key":"18_CR8","unstructured":"Brehob, M., Enbody, R., Torng, E., Wagner, S.: On-line restricted caching. In: Proc. 12th Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 374\u2013383 (2001)"},{"issue":"1","key":"18_CR9","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1109\/TC.2004.1255792","volume":"53","author":"M. Brehob","year":"2004","unstructured":"Brehob, M., Enbody, R., Wagner, S., Torng, E.: Optimal replacement is np-hard for nonstandard caches. IEEE Transactions on Computers\u00a053(1), 73\u201376 (2004)","journal-title":"IEEE Transactions on Computers"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Chen, S., Naor, J.: Competitive analysis via regularization. In: SODA, pp. 436\u2013444 (2014)","DOI":"10.1137\/1.9781611973402.32"},{"key":"18_CR11","unstructured":"Buchbinder, N., Chen, S., Naor, J., Shamir, O.: Unified algorithms for online learning and competitive analysis. In: COLT, pp. 5.1\u20135.18 (2012)"},{"issue":"2-3","key":"18_CR12","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science\u00a03(2-3), 93\u2013263 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"issue":"2","key":"18_CR13","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0095-8956(84)90023-6","volume":"36","author":"W.H. Cunningham","year":"1984","unstructured":"Cunningham, W.H.: Testing membership in matroid polyhedra. Journal of Combinatorial Theory, Series B\u00a036(2), 161\u2013188 (1984)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"18_CR14","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Combinatorial Structures and Their Applications, pp. 69\u201387 (1970)"},{"issue":"1","key":"18_CR15","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J. Edmonds","year":"1971","unstructured":"Edmonds, J.: Matroids and the greedy algorithm. Mathematical Programming\u00a01(1), 127\u2013136 (1971)","journal-title":"Mathematical Programming"},{"issue":"3","key":"18_CR16","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00607-007-0230-6","volume":"80","author":"L. Epstein","year":"2007","unstructured":"Epstein, L., van Stee, R.: Calculating lower bounds for caching problems. Computing\u00a080(3), 275\u2013285 (2007)","journal-title":"Computing"},{"issue":"4","key":"18_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. Journal of Algorithms\u00a012(4), 685\u2013699 (1991)","journal-title":"Journal of Algorithms"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/3-540-45749-6_45","volume-title":"Algorithms - ESA 2002","author":"A. Fiat","year":"2002","unstructured":"Fiat, A., Mendel, M., Seiden, S.S.: Online companion caching. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 499\u2013511. Springer, Heidelberg (2002)"},{"key":"18_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-662-43948-7_47","volume-title":"Automata, Languages, and Programming","author":"A. Gupta","year":"2014","unstructured":"Gupta, A., Talwar, K., Wieder, U.: Changing bases: Multistage optimization for matroids and matchings. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol.\u00a08572, pp. 563\u2013575. Springer, Heidelberg (2014)"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"Harary, F., Welsh, D.: Matroids versus graphs. In: The Many Facets of Graph Theory. Lecture Notes in Mathematics, vol.\u00a0110, pp. 155\u2013170 (1969)","DOI":"10.1007\/BFb0060114"},{"issue":"1-6","key":"18_CR21","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"L.A. McGeoch","year":"1991","unstructured":"McGeoch, L.A., Sleator, D.D.: A strongly competitive randomized paging algorithm. Algorithmica\u00a06(1-6), 816\u2013825 (1991)","journal-title":"Algorithmica"},{"key":"18_CR22","unstructured":"Peserico, E.: Online paging with arbitrary associativity. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 555\u2013564 (2003)"},{"key":"18_CR23","unstructured":"Schrijver, A.: Combinatorial Optimization: polyhedra and efficiency. Springer (2003)"},{"issue":"2","key":"18_CR24","doi-asserted-by":"publisher","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. Communication of the ACM\u00a028(2), 202\u2013208 (1985)","journal-title":"Communication of the ACM"},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J., Chekuri, C., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proc. of the 43rd Annual ACM Symposium on Theory of Computing, pp. 783\u2013792 (2011)","DOI":"10.1145\/1993636.1993740"},{"issue":"3","key":"18_CR26","doi-asserted-by":"publisher","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H. Whitney","year":"1935","unstructured":"Whitney, H.: On the abstract properties of linear dependence. American Journal of Mathematics\u00a057(3), 509\u2013533 (1935)","journal-title":"American Journal of Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44777-2_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T16:22:34Z","timestamp":1558974154000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44777-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662447765","9783662447772"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44777-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}