{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:37Z","timestamp":1740109297744,"version":"3.37.3"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,10,29]],"date-time":"2019-10-29T00:00:00Z","timestamp":1572307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,10,29]],"date-time":"2019-10-29T00:00:00Z","timestamp":1572307200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"DOI":"10.1007\/s00453-019-00638-w","type":"journal-article","created":{"date-parts":[[2019,10,30]],"date-time":"2019-10-30T20:31:57Z","timestamp":1572467517000},"page":"1101-1135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Stochastic Dominance and the Bijective Ratio of Online Algorithms"],"prefix":"10.1007","volume":"82","author":[{"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7152-4192","authenticated-orcid":false,"given":"Marc P.","family":"Renault","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,29]]},"reference":[{"key":"638_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Czumaj, A., Englert, M., R\u00e4cke, H.: Almost tight bounds for reordering buffer management. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 607\u2013616 (2011)","DOI":"10.1145\/1993636.1993717"},{"key":"638_CR2","doi-asserted-by":"crossref","unstructured":"Anagnostopoulos, A., Dombry, C., Guillotin-Plantard, N., Kontoyiannis, I., Upfal, E.: Stochastic analysis of the k-server problem on the circle. In: Proceedings of the 21st International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA), pp. 21\u201334 (2010)","DOI":"10.46298\/dmtcs.2791"},{"key":"638_CR3","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-Ortiz, A.: List update with locality of reference. In: Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN), pp. 399\u2013410 (2008)","DOI":"10.1007\/978-3-540-78773-0_35"},{"issue":"3","key":"638_CR4","doi-asserted-by":"crossref","first-page":"1152","DOI":"10.1007\/s00453-018-0461-2","volume":"81","author":"S Angelopoulos","year":"2019","unstructured":"Angelopoulos, S., Dorrigiv, R., L\u00f3pez-Ortiz, A.: On the separation and equivalence of paging strategies and other online algorithms. Algorithmica 81(3), 1152\u20131179 (2019)","journal-title":"Algorithmica"},{"issue":"2","key":"638_CR5","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/2450142.2450143","volume":"60","author":"S Angelopoulos","year":"2013","unstructured":"Angelopoulos, S., Schweitzer, P.: Paging and list update under bijective analysis. J. ACM 60(2), 7:1\u20137:18 (2013)","journal-title":"J. ACM"},{"key":"638_CR6","doi-asserted-by":"crossref","unstructured":"Avigdor-Elgrabli, N., Rabani, Y.: An optimal randomized online algorithm for reordering buffer management. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1\u201310 (2013)","DOI":"10.1109\/FOCS.2013.9"},{"issue":"4","key":"638_CR7","doi-asserted-by":"crossref","first-page":"35:1","DOI":"10.1145\/2663347","volume":"11","author":"N Avigdor-Elgrabli","year":"2015","unstructured":"Avigdor-Elgrabli, N., Rabani, Y.: An improved competitive algorithm for reordering buffer management. ACM Trans. Algorithms 11(4), 35:1\u201335:15 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"638_CR8","doi-asserted-by":"crossref","first-page":"19:1","DOI":"10.1145\/2339123.2339126","volume":"59","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Buchbinder, N., Naor, J.: A primal-dual randomized algorithm for weighted paging. J. ACM 59(4), 19:1\u201319:24 (2012)","journal-title":"J. ACM"},{"issue":"2\u20133","key":"638_CR9","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.tcs.2004.06.001","volume":"324","author":"Y Bartal","year":"2004","unstructured":"Bartal, Y., Koutsoupias, E.: On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci. 324(2\u20133), 337\u2013345 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"638_CR10","doi-asserted-by":"crossref","first-page":"325","DOI":"10.2498\/cit.1001140","volume":"15","author":"A Baumgartner","year":"2007","unstructured":"Baumgartner, A., Manger, R., Hocenski, Z.: Work function algorithm with a moving window for solving the on-line k-server problem. J. Comput. Inf. Technol. 15(4), 325\u2013330 (2007)","journal-title":"J. Comput. Inf. Technol."},{"issue":"1","key":"638_CR11","doi-asserted-by":"crossref","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":"638_CR12","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":"4","key":"638_CR13","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/s00453-003-1036-3","volume":"37","author":"A Borodin","year":"2003","unstructured":"Borodin, A., Nielsen, M.N., Rackoff, C.: (Incremental) priority algorithms. Algorithmica 37(4), 295\u2013326 (2003)","journal-title":"Algorithmica"},{"issue":"7\u20138","key":"638_CR14","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/s00236-010-0123-6","volume":"47","author":"J Boyar","year":"2010","unstructured":"Boyar, J., Ehmsen, M.R., Larsen, K.S.: A theoretical comparison of LRU and LRU-K. Acta Inform. 47(7\u20138), 359\u2013374 (2010)","journal-title":"Acta Inform."},{"key":"638_CR15","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/978-3-319-98355-4_13","volume-title":"Adventures Between Lower Bounds and Higher Altitudes. LNCS","author":"J Boyar","year":"2018","unstructured":"Boyar, J., Favrholdt, L., Larsen, K.: Relative worst-order analysis: a survey. In: B\u00f6ckenhauer, H.J., Komm, D., Unger, W. (eds.) Adventures Between Lower Bounds and Higher Altitudes. LNCS, vol. 11011, pp. 216\u2013230. Springer, Berlin (2018)"},{"issue":"5","key":"638_CR16","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1016\/j.jcss.2007.03.001","volume":"73","author":"J Boyar","year":"2007","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S.: The relative worst-order ratio applied to paging. J. Comput. Syst. Sci. 73(5), 818\u2013843 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"638_CR17","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1007\/s00453-014-9884-6","volume":"72","author":"J Boyar","year":"2015","unstructured":"Boyar, J., Irani, S., Larsen, K.S.: A comparison of performance measures for online algorithms. Algorithmica 72(4), 969\u2013994 (2015)","journal-title":"Algorithmica"},{"issue":"1","key":"638_CR18","doi-asserted-by":"crossref","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."},{"issue":"4","key":"638_CR19","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1287\/moor.10.4.585","volume":"10","author":"AR Calderbank","year":"1985","unstructured":"Calderbank, A.R., Coffman Jr., E.G., Flatto, L.: Sequencing problems in two-server systems. Math. Oper. Res. 10(4), 585\u2013598 (1985)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"638_CR20","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1080\/15326348508807002","volume":"1","author":"AR Calderbank","year":"1985","unstructured":"Calderbank, A.R., Coffman Jr., E.G., Flatto, L.: Sequencing two servers on a sphere. Commun. Stat. Stoch. Models 1(1), 17\u201328 (1985)","journal-title":"Commun. Stat. Stoch. Models"},{"issue":"2","key":"638_CR21","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(2), 172\u2013181 (1991)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"638_CR22","doi-asserted-by":"crossref","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."},{"key":"638_CR23","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1090\/dimacs\/007\/02","volume":"7","author":"M Chrobak","year":"1992","unstructured":"Chrobak, M., Larmore, L.L.: The server problem and on-line games. DIMACS Ser. Discrete Math. Theor. Comput. Sci. 7, 11\u201364 (1992)","journal-title":"DIMACS Ser. Discrete Math. Theor. Comput. Sci."},{"issue":"3","key":"638_CR24","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/1086649.1086670","volume":"36","author":"R Dorrigiv","year":"2005","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A.: A survey of performance measures for on-line algorithms. SIGACT News 36(3), 67\u201381 (2005)","journal-title":"SIGACT News"},{"key":"638_CR25","unstructured":"Garg, N., Gupta, A., Leonardi, S., Sankowski, P.: Stochastic analyses for online combinatorial optimization problems. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 942\u2013951 (2008)"},{"issue":"9","key":"638_CR26","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"638_CR27","doi-asserted-by":"crossref","unstructured":"Hiller, B., Vredeveld, T.: Probabilistic analysis of online bin coloring algorithms via stochastic comparison. In: Proceedings of the 16th Annual European Symposium on Algorithms (ESA), pp. 528\u2013539 (2008)","DOI":"10.1007\/978-3-540-87744-8_44"},{"key":"638_CR28","unstructured":"Hiller, B., Vredeveld, T.: Simple optimality proofs for least recently used in the presence of locality of reference. Technical report, Maastricht University of Business and Economics (2009)"},{"issue":"3","key":"638_CR29","first-page":"189","volume":"27","author":"B Hiller","year":"2012","unstructured":"Hiller, B., Vredeveld, T.: Probabilistic alternatives for competitive analysis. Comput. Sci. R&D 27(3), 189\u2013196 (2012)","journal-title":"Comput. Sci. R&D"},{"issue":"2","key":"638_CR30","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0020-0190(83)90030-3","volume":"16","author":"M Hofri","year":"1983","unstructured":"Hofri, M.: Should the two-headed disk be greedy?\u2014Yes, it should. Inf. Process. Lett. 16(2), 83\u201385 (1983)","journal-title":"Inf. Process. Lett."},{"key":"638_CR31","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF01236981","volume":"141","author":"M Keane","year":"1975","unstructured":"Keane, M.: Interval exchange transformations. Math. Z. 141, 25\u201331 (1975)","journal-title":"Math. Z."},{"key":"638_CR32","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 359\u2013364 (1996)"},{"issue":"2","key":"638_CR33","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.cosrev.2009.04.002","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E.: The k-server problem. Comput. Sci. Rev. 3(2), 105\u2013118 (2009)","journal-title":"Comput. Sci. Rev."},{"key":"638_CR34","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/S0097539796299540","volume":"30","author":"E Koutsoupias","year":"2000","unstructured":"Koutsoupias, E., Papadimitriou, C.: Beyond competitive analysis. SIAM J. Comput. 30, 300\u2013317 (2000)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"638_CR35","doi-asserted-by":"crossref","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)","journal-title":"J. ACM"},{"issue":"1","key":"638_CR36","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1080\/15427951.2007.10129136","volume":"4","author":"SS Lumetta","year":"2007","unstructured":"Lumetta, S.S., Mitzenmacher, M.: Using the power of two choices to improve bloom filters. Internet Math. 4(1), 17\u201333 (2007)","journal-title":"Internet Math."},{"key":"638_CR37","doi-asserted-by":"crossref","unstructured":"Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for on-line problems. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computation (STOC), pp. 322\u2013333 (1988)","DOI":"10.1145\/62212.62243"},{"issue":"3","key":"638_CR38","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1006\/jcss.1996.0072","volume":"53","author":"M Mitzenmacher","year":"1996","unstructured":"Mitzenmacher, M.: Bounds on the greedy routing algorithm for array networks. J. Comput. Syst. Sci. 53(3), 317\u2013327 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"638_CR39","volume-title":"Comparison Methods for Stochastic Models and Risks","author":"A M\u00fcller","year":"2002","unstructured":"M\u00fcller, A., Stoyan, D.: Comparison Methods for Stochastic Models and Risks. Wiley, Hoboken (2002)"},{"key":"638_CR40","doi-asserted-by":"crossref","first-page":"820","DOI":"10.1007\/3-540-45749-6_71","volume-title":"Algorithms \u2014 ESA 2002","author":"Harald R\u00e4cke","year":"2002","unstructured":"R\u00e4cke, H., Sohler, C., Westermann, M.: Online scheduling for sorting buffers. In: Proceedings of the 10th Annual European Symposium on Algorithms (ESA), pp. 820\u2013832 (2002)"},{"issue":"6","key":"638_CR41","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1147\/rd.386.0683","volume":"38","author":"P Raghavan","year":"1994","unstructured":"Raghavan, P., Snir, M.: Memory versus randomization in on-line algorithms. IBM J. Res. Dev. 38(6), 683\u2013708 (1994)","journal-title":"IBM J. Res. Dev."},{"issue":"4","key":"638_CR42","doi-asserted-by":"crossref","first-page":"361","DOI":"10.2498\/cit.1001922","volume":"18","author":"T Rudec","year":"2010","unstructured":"Rudec, T., Baumgartner, A., Manger, R.: Measuring true performance of the work function algorithm for solving the on-line k-server problem. J. Comput. Inf. Technol. 18(4), 361\u2013367 (2010)","journal-title":"J. Comput. Inf. Technol."},{"issue":"1","key":"638_CR43","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s10100-011-0222-7","volume":"21","author":"T Rudec","year":"2013","unstructured":"Rudec, T., Baumgartner, A., Manger, R.: A fast work function algorithm for solving the k-server problem. Cent. Eur. J. Oper. Res. 21(1), 187\u2013205 (2013)","journal-title":"Cent. Eur. J. Oper. Res."},{"issue":"5","key":"638_CR44","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0020-0190(95)00210-3","volume":"57","author":"S Seshadri","year":"1996","unstructured":"Seshadri, S., Rotem, D.: The two headed disk: stochastic dominance of the greedy policy. Inf. Process. Lett. 57(5), 273\u2013277 (1996)","journal-title":"Inf. Process. Lett."},{"key":"638_CR45","volume-title":"Stochastic Orders and Their Applications","author":"M Shaked","year":"1994","unstructured":"Shaked, M., Shanthikumar, J.G.: Stochastic Orders and Their Applications. Academic Press, Cambridge (1994)"},{"key":"638_CR46","doi-asserted-by":"crossref","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. Commun. ACM 28, 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"638_CR47","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511625787","volume-title":"Topics in Microeconomics","author":"E Wolfstetter","year":"1999","unstructured":"Wolfstetter, E.: Topics in Microeconomics. Cambridge University Press, Cambridge (1999)"},{"key":"638_CR48","unstructured":"Young, N.E.: On-line caching as cache size varies. In: Proceedings of the 2nd Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms (SODA), pp. 241\u2013250 (1991)"},{"issue":"6","key":"638_CR49","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"NE Young","year":"1994","unstructured":"Young, N.E.: The $$k$$-server dual and loose competitiveness for paging. Algorithmica 11(6), 525\u2013541 (1994)","journal-title":"Algorithmica"},{"key":"638_CR50","unstructured":"Young, N.E.: Bounding the diffuse adversary. In: Proceedings of the 9th Annual ACM-SIAM symposium on Discrete Algorithms (SODA), pp. 420\u2013425 (1998)"},{"issue":"1","key":"638_CR51","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1006\/jagm.2000.1099","volume":"37","author":"NE Young","year":"2000","unstructured":"Young, N.E.: On-line paging against adversarially biased random inputs. J. Algorithms 37(1), 218\u2013235 (2000)","journal-title":"J. Algorithms"},{"issue":"3","key":"638_CR52","doi-asserted-by":"crossref","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)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00638-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00638-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00638-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T23:48:09Z","timestamp":1721951289000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00638-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,29]]},"references-count":52,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["638"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00638-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,10,29]]},"assertion":[{"value":"21 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}