{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T18:21:13Z","timestamp":1758478873077,"version":"3.37.3"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T00:00:00Z","timestamp":1729123200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T00:00:00Z","timestamp":1729123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"crossref","award":["CCF-1536026","CCF-1527084"],"award-info":[{"award-number":["CCF-1536026","CCF-1527084"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"crossref","award":["CCF-1535929","CCF-1619463"],"award-info":[{"award-number":["CCF-1535929","CCF-1619463"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF2110230"],"award-info":[{"award-number":["W911NF2110230"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-2039945"],"award-info":[{"award-number":["IIS-2039945"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,1]]},"abstract":"Abstract<\/jats:title>\n It is natural to generalize the online \n \n $$k$$<\/jats:tex-math>\n \n k<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-Server problem by allowing each request to specify not only a point p<\/jats:italic>, but also a subset S<\/jats:italic> of servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p<\/jats:italic>, but also a subset S<\/jats:italic> of cache slots, and is satisfied by having a copy of p<\/jats:italic> in some slot in S<\/jats:italic>. We call this problem Slot-Heterogenous Paging<\/jats:italic>. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family \n \n $${\\mathcal {S}}\\subseteq 2^{[k]}$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \u2286<\/mml:mo>\n \n 2<\/mml:mn>\n \n [<\/mml:mo>\n k<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k<\/jats:italic> and family \n \n $${\\mathcal {S}}$$<\/jats:tex-math>\n \n S<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>:\n \n If all request sets are allowed (\n \n $${\\mathcal {S}}=2^{[k]}\\setminus \\{\\emptyset \\}$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n =<\/mml:mo>\n \n 2<\/mml:mn>\n \n [<\/mml:mo>\n k<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \\<\/mml:mo>\n \n {<\/mml:mo>\n \u2205<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging (\n \n $${\\mathcal {S}}=\\{[k]\\}$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n =<\/mml:mo>\n {<\/mml:mo>\n [<\/mml:mo>\n k<\/mml:mi>\n ]<\/mml:mo>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>).<\/jats:p>\n <\/jats:list-item>\n \n As a function of \n \n $$|{\\mathcal {S}}|$$<\/jats:tex-math>\n \n \n |<\/mml:mo>\n S<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and k<\/jats:italic>, the optimal deterministic ratio is polynomial: at most \n \n $$O(k^2|{\\mathcal {S}}|)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n |<\/mml:mo>\n S<\/mml:mi>\n |<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and at least \n \n $$\\Omega (\\sqrt{|{\\mathcal {S}}|})$$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n \n \n |<\/mml:mo>\n S<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>.<\/jats:p>\n <\/jats:list-item>\n \n For any laminar family \n \n $${\\mathcal {S}}$$<\/jats:tex-math>\n \n S<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of height h<\/jats:italic>, the optimal ratios are O<\/jats:italic>(hk<\/jats:italic>) (deterministic) and \n \n $$O(h^2\\log k)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n h<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n log<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> (randomized).<\/jats:p>\n <\/jats:list-item>\n \n The special case of laminar \n \n $${\\mathcal {S}}$$<\/jats:tex-math>\n \n S<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> that we call All-or-One Paging<\/jats:italic> extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted<\/jats:italic> All-or-One Paging is \n \n $$\\Theta (k)$$<\/jats:tex-math>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Offline All-or-One Paging is \n \n $$\\mathbb{N}\\mathbb{P}$$<\/jats:tex-math>\n \n \n N<\/mml:mi>\n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-hard.<\/jats:p>\n <\/jats:list-item>\n <\/jats:list> Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set \n \n $$P$$<\/jats:tex-math>\n \n P<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of pages<\/jats:italic>, and is satisfied by fetching any page from \n \n $$P$$<\/jats:tex-math>\n \n P<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> into the cache. The optimal ratios for the latter problem (with laminar family of height h<\/jats:italic>) are at most hk<\/jats:italic> (deterministic) and \n \n $$hH_k$$<\/jats:tex-math>\n \n \n h<\/mml:mi>\n \n H<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> (randomized).<\/jats:p>","DOI":"10.1007\/s00453-024-01270-z","type":"journal-article","created":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T11:02:16Z","timestamp":1729162936000},"page":"89-131","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Paging with Heterogeneous Cache Slots"],"prefix":"10.1007","volume":"87","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[]},{"given":"Samuel","family":"Haney","sequence":"additional","affiliation":[]},{"given":"Mehraneh","family":"Liaee","sequence":"additional","affiliation":[]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[]},{"given":"Ravi","family":"Sundaram","sequence":"additional","affiliation":[]},{"given":"Neal E.","family":"Young","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,17]]},"reference":[{"issue":"1\u20132","key":"1270_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). https:\/\/doi.org\/10.1016\/S0304-3975(98)00116-9","journal-title":"Theor. Comput. Sci."},{"key":"1270_CR2","doi-asserted-by":"publisher","unstructured":"Argue, C.J., Gupta, A., Tang, Z., Guruganesh, G.: Chasing convex bodies with linear competitive ratio. J. ACM 68(5), 32:1-32:10 (2021). https:\/\/doi.org\/10.1145\/3450349","DOI":"10.1145\/3450349"},{"key":"1270_CR3","doi-asserted-by":"publisher","unstructured":"Ayyadevara, N., Chiplunkar, A.: The randomized competitive ratio of weighted k-server is at least exponential. In: Mutzel, P., Pagh, R., Herman, G. (eds.) 29th Annual European Symposium on Algorithms, ESA 2021, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pp. 9:1\u20139:11. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2021. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.9, https:\/\/doi.org\/10.4230\/LIPICS.ESA.2021.9","DOI":"10.4230\/LIPICS.ESA.2021.9"},{"key":"1270_CR4","doi-asserted-by":"publisher","DOI":"10.1145\/2783434","author":"N Bansal","year":"2015","unstructured":"Bansal, N., Buchbinder, N., Madry, A., Naor, J.: A polylogarithmic-competitive algorithm for the k-server problem. J. ACM (2015). https:\/\/doi.org\/10.1145\/2783434","journal-title":"J. ACM"},{"key":"1270_CR5","doi-asserted-by":"publisher","unstructured":"Bansal, N., Buchbinder, N., Naor, J.: A primal-dual randomized algorithm for weighted paging. J. ACM 59(4), 19:1-19:24 (2012). https:\/\/doi.org\/10.1145\/2339123.2339126","DOI":"10.1145\/2339123.2339126"},{"key":"1270_CR6","doi-asserted-by":"publisher","unstructured":"Bansal, N., Eli\u00e1s, M., Koumoutsos, G.: Weighted k-server bounds via combinatorial dichotomies. In: Umans, C. (ed) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, October 15-17, 2017, pp. 493\u2013504. IEEE Computer Society, (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.52","DOI":"10.1109\/FOCS.2017.52"},{"key":"1270_CR7","doi-asserted-by":"publisher","unstructured":"Bansal, N., Eli\u00e1s, M., Koumoutsos, G., Nederlof, J.: Competitive algorithms for generalized k-server in uniform metrics. ACM Trans. Algorithms 19(1), 8:1-8:15 (2023). https:\/\/doi.org\/10.1145\/3568677","DOI":"10.1145\/3568677"},{"key":"1270_CR8","doi-asserted-by":"publisher","unstructured":"Bansal, N., Naor, J., Talmon, O.: Efficient online weighted multi-level paging. In: Agrawal, K., Azar, Y. (eds.) SPAA \u201921: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, 2021, pp. 94\u2013104. ACM, (2021). https:\/\/doi.org\/10.1145\/3409964.3461801","DOI":"10.1145\/3409964.3461801"},{"key":"1270_CR9","doi-asserted-by":"publisher","unstructured":"Beckmann, N., Gibbons, P.B., Haeupler, B., McGuffey, C.: Writeback-aware caching. In: Maggs, B.M. (ed) 1st Symposium on Algorithmic Principles of Computer Systems, APOCS 2020, Salt Lake City, 2020, pp. 1\u201315. SIAM, (2020). https:\/\/doi.org\/10.1137\/1.9781611976021.1","DOI":"10.1137\/1.9781611976021.1"},{"issue":"2","key":"1270_CR10","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). https:\/\/doi.org\/10.1147\/sj.52.0078","journal-title":"IBM Syst. J."},{"issue":"2","key":"1270_CR11","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 virtual-storage computer. IBM Syst. J. 5(2), 78\u2013101 (1966). https:\/\/doi.org\/10.1147\/sj.52.0078","journal-title":"IBM Syst. J."},{"key":"1270_CR12","doi-asserted-by":"publisher","unstructured":"Bienkowski, M., Je\u017c, \u0141., Schmidt, P.: Slaying hydrae: improved bounds for generalized k-server in uniform metrics. In: Lu, P., Zhang, G., (eds.) 30th International Symposium on Algorithms and Computation, ISAAC 2019, volume 149 of LIPIcs, pp. 14:1\u201314:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2019.14","DOI":"10.4230\/LIPIcs.ISAAC.2019.14"},{"key":"1270_CR13","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":"2","key":"1270_CR14","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1006\/inco.1998.2775","volume":"150","author":"A Borodin","year":"1999","unstructured":"Borodin, A., El-Yaniv, R.: On randomization in on-line computation. Inf. Comput. 150(2), 244\u2013267 (1999). https:\/\/doi.org\/10.1006\/inco.1998.2775","journal-title":"Inf. Comput."},{"issue":"4","key":"1270_CR15","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1145\/146585.146588","volume":"39","author":"A Borodin","year":"1992","unstructured":"Borodin, A., Linial, N., Saks, M.E.: An optimal on-line algorithm for metrical task system. J. ACM 39(4), 745\u2013763 (1992). https:\/\/doi.org\/10.1145\/146585.146588","journal-title":"J. ACM"},{"issue":"2","key":"1270_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1023\/A:1022989909868","volume":"6","author":"M Brehob","year":"2003","unstructured":"Brehob, M., Enbody, R.J., Torng, E., Wagner, S.: On-line restricted caching. J. Sched. 6(2), 149\u2013166 (2003). https:\/\/doi.org\/10.1023\/A:1022989909868","journal-title":"J. Sched."},{"issue":"1","key":"1270_CR17","doi-asserted-by":"publisher","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.J.: Optimal replacement is NP-hard for nonstandard caches. IEEE Trans. Comput. 53(1), 73\u201376 (2004). https:\/\/doi.org\/10.1109\/TC.2004.1255792","journal-title":"IEEE Trans. Comput."},{"key":"1270_CR18","doi-asserted-by":"publisher","unstructured":"Bubeck, S., Coester, C., Rabani, Y.: The randomized k-server conjecture is false! In: Saha, B., Servedio, R.A. (eds.) Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, 2023, pp. 581\u2013594. ACM (2023). https:\/\/doi.org\/10.1145\/3564246.3585132","DOI":"10.1145\/3564246.3585132"},{"key":"1270_CR19","doi-asserted-by":"publisher","unstructured":"Bubeck, S., Cohen, M.B., Lee, Y.T., Lee, J.R., Ma\u0327dry, A.: K-server via multiscale entropic regularization. In: Diakonikolas, I., Kempe, D., Henzinger, M., (eds.) Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, 2018, pp. 3\u201316. ACM (2018). https:\/\/doi.org\/10.1145\/3188745.3188798","DOI":"10.1145\/3188745.3188798"},{"key":"1270_CR20","doi-asserted-by":"crossref","unstructured":"Bubeck, S., Rabani, Y., Sellke, M.: Online multiserver convex chasing and optimization. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2093\u20132104. SIAM, (2021)","DOI":"10.1137\/1.9781611976465.125"},{"key":"1270_CR21","doi-asserted-by":"publisher","unstructured":"Buchbinder, N., Chen, S., Naor, J.: Competitive algorithms for restricted caching and matroid caching. In: Schulz, A.S., Wagner, D. (eds.) Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, 2014. Proceedings, volume 8737 of Lecture Notes in Computer Science, pp. 209\u2013221. Springer, (2014). https:\/\/doi.org\/10.1007\/978-3-662-44777-2_18","DOI":"10.1007\/978-3-662-44777-2_18"},{"issue":"2","key":"1270_CR22","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/S10107-022-01815-6","volume":"197","author":"N Buchbinder","year":"2023","unstructured":"Buchbinder, N., Coester, C., Naor, J.: Online k-taxi via double coverage and time-reverse primal-dual. Math. Program. 197(2), 499\u2013527 (2023). https:\/\/doi.org\/10.1007\/S10107-022-01815-6","journal-title":"Math. Program."},{"key":"1270_CR23","doi-asserted-by":"crossref","unstructured":"Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., Meyer\u00a0auf der Heide, F.: The k-server with preferences problem. In: SPAA \u201922: 34rd ACM Symposium on Parallelism in Algorithms and Architectures (2022). URL https:\/\/arxiv.org\/abs\/2205.11102","DOI":"10.1145\/3490148.3538595"},{"issue":"1","key":"1270_CR24","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00453-014-9903-7","volume":"71","author":"A Chiplunkar","year":"2015","unstructured":"Chiplunkar, A., Vishwanathan, S.: Metrical service systems with multiple servers. Algorithmica 71(1), 219\u2013231 (2015). https:\/\/doi.org\/10.1007\/s00453-014-9903-7","journal-title":"Algorithmica"},{"key":"1270_CR25","doi-asserted-by":"publisher","DOI":"10.1145\/3365002","author":"A Chiplunkar","year":"2019","unstructured":"Chiplunkar, A., Vishwanathan, S.: Randomized memoryless algorithms for the weighted and the generalized k-server problems. ACM Trans. Algorithms (2019). https:\/\/doi.org\/10.1145\/3365002","journal-title":"ACM Trans. Algorithms"},{"key":"1270_CR26","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Haney, S., Liaee, M., Panigrahi, D., Rajaraman, R., Sundaram, R., Young, N.E.: Online paging with heterogeneous cache slots. In: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), (2023)","DOI":"10.1007\/s00453-024-01270-z"},{"issue":"2","key":"1270_CR27","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)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1270_CR28","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1137\/0220008","volume":"20","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Larmore, L.L.: An optimal on-line algorithm for k-servers on trees. SIAM J. Comput. 20(1), 144\u2013148 (1991)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1270_CR29","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1006\/jagm.1999.1061","volume":"34","author":"M Chrobak","year":"2000","unstructured":"Chrobak, M., Noga, J.: Competitive algorithms for relaxed list update and multilevel caching. J. Algorithms 34(2), 282\u2013308 (2000). https:\/\/doi.org\/10.1006\/jagm.1999.1061","journal-title":"J. Algorithms"},{"issue":"4","key":"1270_CR30","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., Haifeng, X.: Caching is hard-even in the fault model. Algorithmica 63(4), 781\u2013794 (2012)","journal-title":"Algorithmica"},{"key":"1270_CR31","doi-asserted-by":"publisher","unstructured":"Coester, C., Koutsoupias, E.: The online $$k$$-taxi problem. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, 2019, pp. 1136\u20131147. ACM (2019). https:\/\/doi.org\/10.1145\/3313276.3316370","DOI":"10.1145\/3313276.3316370"},{"key":"1270_CR32","doi-asserted-by":"publisher","unstructured":"Christian, C., Elias, K. Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle. In: 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021(July), pp. 12\u201316: Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pp. 57:1\u201357:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 2021 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.57","DOI":"10.4230\/LIPIcs.ICALP.2021.57"},{"key":"1270_CR33","doi-asserted-by":"publisher","DOI":"10.1145\/2086696.2086714","author":"L Domnitser","year":"2012","unstructured":"Domnitser, L., Jaleel, A., Loew, J., Abu-Ghazaleh, N., Ponomarev, D.: Non-monopolizable caches: low-complexity mitigation of cache side channel attacks. ACM Trans. Archit. Code Optim. (2012). https:\/\/doi.org\/10.1145\/2086696.2086714","journal-title":"ACM Trans. Archit. Code Optim."},{"key":"1270_CR34","doi-asserted-by":"publisher","unstructured":"Feuerstein, E.: Uniform service systems with k servers. In: Goos, G., Hartmanis, J., van Leeuwen, J., Lucchesi, C.L., Moura, A.V. (eds.) LATIN\u201998: Theoretical Informatics, volume 1380, pages 23\u201332, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg. https:\/\/doi.org\/10.1007\/BFb0054307","DOI":"10.1007\/BFb0054307"},{"issue":"4","key":"1270_CR35","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). https:\/\/doi.org\/10.1016\/0196-6774(91)90041-V","journal-title":"J. Algorithms"},{"issue":"1","key":"1270_CR36","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(94)90154-6","volume":"130","author":"A Fiat","year":"1994","unstructured":"Fiat, A., Ricklin, M.: Competitive algorithms for the weighted server problem. Theor. Comput. Sci. 130(1), 85\u201399 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90154-6","journal-title":"Theor. Comput. Sci."},{"key":"1270_CR37","unstructured":"Haney, S.: Algorithms for Networks With Uncertainty. PhD thesis, Duke University, (2019). URL https:\/\/dukespace.lib.duke.edu\/dspace\/handle\/10161\/18661"},{"key":"1270_CR38","doi-asserted-by":"crossref","unstructured":"Kamali, S., Xu, H.: Multicore paging algorithms cannot be competitive. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 547\u2013549 (2020)","DOI":"10.1145\/3350755.3400270"},{"key":"1270_CR39","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF01762111","volume":"3","author":"AR Karlin","year":"1988","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. Algorithmica 3, 77\u2013119 (1988). https:\/\/doi.org\/10.1007\/BF01762111","journal-title":"Algorithmica"},{"issue":"1","key":"1270_CR40","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00453-012-9629-3","volume":"66","author":"C Koufogiannakis","year":"2013","unstructured":"Koufogiannakis, C., Young, N.E.: Greedy $$\\delta $$-approximation algorithm for covering with arbitrary constraints and submodular cost. Algorithmica 66(1), 113\u2013152 (2013). https:\/\/doi.org\/10.1007\/s00453-012-9629-3","journal-title":"Algorithmica"},{"issue":"5","key":"1270_CR41","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1145\/210118.210128","volume":"42","author":"E Koutsoupias","year":"1995","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. J. ACM 42(5), 971\u2013983 (1995). https:\/\/doi.org\/10.1145\/210118.210128","journal-title":"J. ACM"},{"issue":"2\u20133","key":"1270_CR42","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.tcs.2004.06.002","volume":"324","author":"Elias Koutsoupias and David Scot Taylor","year":"2004","unstructured":"Elias Koutsoupias and David Scot Taylor: The CNN problem and other k-server variants. Theor. Comput. Sci. 324(2\u20133), 347\u2013359 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.06.002","journal-title":"Theor. Comput. Sci."},{"key":"1270_CR43","doi-asserted-by":"crossref","unstructured":"Lee, J.R.: Erratum:fusible HSTs and the randomized k-server conjecture (2018). URL https:\/\/homes.cs.washington.edu\/~jrl\/papers\/kserver-erratum.html","DOI":"10.1109\/FOCS.2018.00049"},{"key":"1270_CR44","doi-asserted-by":"crossref","unstructured":"Lee, J.R.: Fusible HSTs and the randomized k-server conjecture. In: IEEE 59th Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris (2018)","DOI":"10.1109\/FOCS.2018.00049"},{"issue":"10","key":"1270_CR45","doi-asserted-by":"publisher","first-page":"6926","DOI":"10.1109\/TWC.2017.2734646","volume":"16","author":"X Li","year":"2017","unstructured":"Li, X., Wang, X., Li, K., Han, Z., Leung, V.C.M.: Collaborative multi-tier caching in heterogeneous networks: modeling, analysis, and design. IEEE Trans. Wirel. Commun. 16(10), 6926\u20136939 (2017)","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"1270_CR46","doi-asserted-by":"publisher","unstructured":"Liu, F., Ge, Q., Yarom, Y., Mckeen, F., Rozas, C., Heiser, G., Lee, R.B.: CATalyst: defeating last-level cache side channel attacks in cloud computing. In: 2016 IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 406\u2013418 (2016). https:\/\/doi.org\/10.1109\/HPCA.2016.7446082","DOI":"10.1109\/HPCA.2016.7446082"},{"issue":"2","key":"1270_CR47","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/0196-6774(90)90003-W","volume":"11","author":"MS Manasse","year":"1990","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms 11(2), 208\u2013230 (1990). https:\/\/doi.org\/10.1016\/0196-6774(90)90003-W","journal-title":"J. Algorithms"},{"key":"1270_CR48","doi-asserted-by":"publisher","unstructured":"McGeoch, L.A., Sleator, D.D.: A strongly competitive randomized paging algorithm. Algorithmica 6(6), 816\u2013825 (1991). https:\/\/doi.org\/10.1007\/BF01759073","DOI":"10.1007\/BF01759073"},{"issue":"2","key":"1270_CR49","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.tcs.2004.05.015","volume":"324","author":"M Mendel","year":"2004","unstructured":"Mendel, M., Seiden, S.S.: Online companion caching. Theor. Comput. Sci. 324(2), 183\u2013200 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.05.015","journal-title":"Theor. Comput. Sci."},{"key":"1270_CR50","unstructured":"Patel, J.: Restricted $$k$$-server problem. Master\u2019s thesis, Michigan State University (2004). URL https:\/\/d.lib.msu.edu\/etd\/32678"},{"key":"1270_CR51","doi-asserted-by":"publisher","unstructured":"Sellke, M.: Chasing convex bodies optimally. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings, pp. 1509\u20131518. Society for Industrial and Applied Mathematics (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.92","DOI":"10.1137\/1.9781611975994.92"},{"issue":"2","key":"1270_CR52","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"Daniel Dominic Sleator and Robert Endre Tarjan","year":"1985","unstructured":"Daniel Dominic Sleator and Robert Endre Tarjan: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985). https:\/\/doi.org\/10.1145\/2786.2793","journal-title":"Commun. ACM"},{"key":"1270_CR53","doi-asserted-by":"crossref","unstructured":"Sundarrajan, A., Feng, M., Kasbekar, M., Sitaraman, R.K.: Footprint descriptors: theory and practice of cache provisioning in a global CDN. In: Proceedings of the 13th International Conference on emerging Networking EXperiments and Technologies, pp. 55\u201367 (2017)","DOI":"10.1145\/3143361.3143368"},{"key":"1270_CR54","doi-asserted-by":"publisher","unstructured":"Wang, Z., Lee, R.B.: New cache designs for thwarting software cache-based side channel attacks. In: Proceedings of the 34th Annual International Symposium on Computer Architecture, ISCA \u201907, pp. 494\u2013505, New York (2007). https:\/\/doi.org\/10.1145\/1250662.1250723","DOI":"10.1145\/1250662.1250723"},{"key":"1270_CR55","doi-asserted-by":"publisher","unstructured":"Xiang, Y., Wang, X., Huang, Z., Wang, Z., Luo, Y., Wang, Z.: Dcaps: dynamic cache allocation with partial sharing. In: Proceedings of the Thirteenth EuroSys Conference, EuroSys \u201918, New York, 2018. Association for Computing Machinery. https:\/\/doi.org\/10.1145\/3190508.3190511","DOI":"10.1145\/3190508.3190511"},{"key":"1270_CR56","doi-asserted-by":"publisher","unstructured":"Ye, Y., West, R., Cheng, Z., Li, Y.: COLORIS: a dynamic cache partitioning system using page coloring. In: 2014 23rd International Conference on Parallel Architecture and Compilation Techniques (PACT), pp. 381\u2013392 (2014). https:\/\/doi.org\/10.1145\/2628071.2628104","DOI":"10.1145\/2628071.2628104"},{"issue":"1","key":"1270_CR57","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10617-015-9168-7","volume":"20","author":"W Zang","year":"2016","unstructured":"Zang, W., Gordon-Ross, A.: CaPPS: cache partitioning with partial sharing for multi-core embedded systems. Des. Autom. Embed. Syst. 20(1), 65\u201392 (2016). https:\/\/doi.org\/10.1007\/s10617-015-9168-7","journal-title":"Des. Autom. Embed. Syst."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01270-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01270-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01270-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T13:24:30Z","timestamp":1737120270000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01270-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,17]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["1270"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01270-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,10,17]]},"assertion":[{"value":"9 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2025","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This article has been updated: Table 1 has been moved from section 3.1 to section 1 for improved clarity.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}