{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:21:26Z","timestamp":1777965686902,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2018,9,27]],"date-time":"2018-09-27T00:00:00Z","timestamp":1538006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"publisher","award":["I-1245-407.6\/2014"],"award-info":[{"award-number":["I-1245-407.6\/2014"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s00607-018-0666-x","type":"journal-article","created":{"date-parts":[[2018,9,27]],"date-time":"2018-09-27T09:46:12Z","timestamp":1538041572000},"page":"1369-1390","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Competitive clustering of stochastic communication patterns on a ring"],"prefix":"10.1007","volume":"101","author":[{"given":"Chen","family":"Avin","sequence":"first","affiliation":[]},{"given":"Louis","family":"Cohen","sequence":"additional","affiliation":[]},{"given":"Mahmoud","family":"Parham","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7798-1711","authenticated-orcid":false,"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,27]]},"reference":[{"key":"666_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek A, Czumaj A, Englert M, R\u00e4cke H (2012) An O(log k)-competitive algorithm for generalized caching. In: Proceedings of 23rd SODA, pp 1681\u20131689","DOI":"10.1137\/1.9781611973099.133"},{"issue":"6","key":"666_CR2","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/s00224-006-1350-7","volume":"39","author":"K Andreev","year":"2006","unstructured":"Andreev K, R\u00e4cke H (2006) Balanced graph partitioning. Theory Comput Syst 39(6):929\u2013939","journal-title":"Theory Comput Syst"},{"key":"666_CR3","doi-asserted-by":"crossref","unstructured":"Avin C, Cohen L, Schmid S (2017) Competitive clustering of stochastic communication patterns on the ring. In: Proceedings of 5th international conference on networked systems (NETYS)","DOI":"10.1007\/978-3-319-59647-1_18"},{"key":"666_CR4","doi-asserted-by":"crossref","unstructured":"Avin C, Loukas A, Pacut M, Schmid S (2016) Online balanced repartitioning. In: Proceedings of 30th international symposium on distributed computing (DISC)","DOI":"10.1007\/978-3-662-53426-7_18"},{"issue":"1","key":"666_CR5","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0304-3975(00)00259-0","volume":"268","author":"Y Bartal","year":"2001","unstructured":"Bartal Y, Charikar M, Indyk P (2001) On page migration and other relaxed task systems. Theor Comput Sci 268(1):43\u201366 Also appeared in Proc.\u00a0of the 8th SODA, pages 43\u201352, 1997","journal-title":"Theor Comput Sci"},{"key":"666_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1109\/TNET.2013.2245676","volume":"22","author":"M Bienkowski","year":"2014","unstructured":"Bienkowski M, Feldmann A, Grassler J, Schaffrath G, Schmid S (2014) The wide-area virtual service migration problem: a competitive analysis approach. IEEE\/ACM Trans Netw 22:165\u2013178","journal-title":"IEEE\/ACM Trans Netw"},{"key":"666_CR7","unstructured":"Black DL, Sleator DD (1989) Competitive algorithms for replication and migration problems. Carnegie-Mellon University, Department of Computer Science, Pittsburgh, USA"},{"issue":"4","key":"666_CR8","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 ME (1992) An optimal on-line algorithm for metrical task system. J ACM 39(4):745\u2013763 Also appeared in Proc.\u00a0of the 19th STOC, pages 373\u2013382, 1987","journal-title":"J ACM"},{"issue":"2","key":"666_CR9","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s00453-013-9793-0","volume":"71","author":"L Epstein","year":"2015","unstructured":"Epstein L, Imreh C, Levin A, Nagy-Gy\u00f6rgy J (2015) Online file caching with rejection penalties. Algorithmica 71(2):279\u2013306","journal-title":"Algorithmica"},{"issue":"4","key":"666_CR10","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1137\/S0097539701387660","volume":"31","author":"U Feige","year":"2002","unstructured":"Feige U, Krauthgamer R (2002) A polylogarithmic approximation of the minimum bisection. SIAM J Comput 31(4):1090\u20131118","journal-title":"SIAM J Comput"},{"issue":"4","key":"666_CR11","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 RM, Luby M, McGeoch LA, Sleator DD, Young NE (1991) Competitive paging algorithms. J Algorithms 12(4):685\u2013699","journal-title":"J Algorithms"},{"issue":"3","key":"666_CR12","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1016\/S0022-0000(05)80060-1","volume":"48","author":"A Fiat","year":"1994","unstructured":"Fiat A, Rabani Y, Ravid Y (1994) Competitive k-server algorithms. J Comput Syst Sci 48(3):410\u2013428","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"666_CR13","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1137\/1007106","volume":"7","author":"W Franck","year":"1965","unstructured":"Franck W (1965) An optimal search problem. SIAM Rev 7(4):503\u2013512","journal-title":"SIAM Rev"},{"issue":"1","key":"666_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/050640904","volume":"48","author":"R Krauthgamer","year":"2006","unstructured":"Krauthgamer R, Feige U (2006) A polylogarithmic approximation of the minimum bisection. SIAM Rev 48(1):99\u2013130","journal-title":"SIAM Rev"},{"issue":"6","key":"666_CR15","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1007\/BF01759073","volume":"6","author":"LA McGeoch","year":"1991","unstructured":"McGeoch LA, Sleator DD (1991) A strongly competitive randomized paging algorithm. Algorithmica 6(6):816\u2013825","journal-title":"Algorithmica"},{"issue":"2\u20133","key":"666_CR16","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 SS (2004) Online companion caching. Theor Comput Sci 324(2\u20133):183\u2013200","journal-title":"Theor Comput Sci"},{"key":"666_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and computing: randomized algorithms and probabilistic analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher M, Upfal E (2005) Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press, New York"},{"issue":"5\u20136","key":"666_CR18","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1007\/BF02179880","volume":"80","author":"T P\u00f6schel","year":"1995","unstructured":"P\u00f6schel T, Ebeling W, Ros\u00e9 H (1995) Guessing probability distributions from small samples. J Stat Phys 80(5\u20136):1443\u20131452","journal-title":"J Stat Phys"},{"issue":"3","key":"666_CR19","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0196-6774(89)90031-X","volume":"10","author":"PV Ramanan","year":"1989","unstructured":"Ramanan PV, Brown DJ, Lee CC, Lee DT (1989) On-line bin packing in linear time. J Algorithms 10(3):305\u2013326","journal-title":"J Algorithms"},{"issue":"5","key":"666_CR20","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/585265.585269","volume":"49","author":"SS Seiden","year":"2002","unstructured":"Seiden SS (2002) On the online bin packing problem. J ACM 49(5):640\u2013671","journal-title":"J ACM"},{"issue":"2","key":"666_CR21","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator DD, Tarjan RE (1985) Amortized efficiency of list update and paging rules. Commun ACM 28(2):202\u2013208","journal-title":"Commun ACM"},{"key":"666_CR22","doi-asserted-by":"crossref","unstructured":"Vaquero L, Cuadrado F, Logothetis D, Martella C (2013) Adaptive partitioning for large-scale dynamic graphs. In: Proceedings of 4th annual symposium on cloud computing (SOCC), pp 35:1\u201335:2","DOI":"10.1145\/2523616.2525943"},{"key":"666_CR23","unstructured":"Young NE (1991) On-line caching as cache size varies. In: Proceedings of the 2nd ACM-SIAM symposium on discrete algorithms (SODA), pp 241\u2013250"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-018-0666-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00607-018-0666-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-018-0666-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T20:27:37Z","timestamp":1569529657000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00607-018-0666-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,27]]},"references-count":23,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["666"],"URL":"https:\/\/doi.org\/10.1007\/s00607-018-0666-x","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,27]]},"assertion":[{"value":"4 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}