{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:47:04Z","timestamp":1750308424908,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T00:00:00Z","timestamp":1564012800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2016\/22\/E\/ST6\/00499 and 2015\/18\/E\/ST6\/00456"],"award-info":[{"award-number":["2016\/22\/E\/ST6\/00499 and 2015\/18\/E\/ST6\/00456"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["677651"],"award-info":[{"award-number":["677651"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            We construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year-old, 4.086-competitive M\n            <jats:sc>ove<\/jats:sc>\n            -T\n            <jats:sc>o<\/jats:sc>\n            -L\n            <jats:sc>ocal<\/jats:sc>\n            -M\n            <jats:sc>in<\/jats:sc>\n            (M\n            <jats:sc>tlm<\/jats:sc>\n            ) algorithm by Bartal et\u00a0al.\u00a0(SODA 1997). Like M\n            <jats:sc>tlm<\/jats:sc>\n            , our algorithm also operates in phases, but it adapts their lengths dynamically depending on the geometry of requests seen so far. The improvement was obtained by carefully analyzing a linear model (factor-revealing linear program) of a single phase of the algorithm. We also show that if an online algorithm operates in phases of fixed length and the adversary is able to modify the graph between phases, then the competitive ratio is at least 4.086.\n          <\/jats:p>","DOI":"10.1145\/3340296","type":"journal-article","created":{"date-parts":[[2019,7,25]],"date-time":"2019-07-25T12:34:33Z","timestamp":1564058073000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Dynamic Beats Fixed"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2453-7772","authenticated-orcid":false,"given":"Marcin","family":"Bienkowski","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaros\u0142aw","family":"Byrka","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, Wroc\u0142aw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Mucha","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/645930.672860"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167142"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366885"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0924"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039752"},{"key":"e_1_2_1_7_1","volume-title":"Dagstul Workshop on On-line Algorithms. 97--117","author":"Bartal Yair","year":"1996","unstructured":"Yair Bartal . 1996 . Distributed paging . In Dagstul Workshop on On-line Algorithms. 97--117 . Yair Bartal. 1996. Distributed paging. In Dagstul Workshop on On-line Algorithms. 97--117."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/314161.314178"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1073"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294260"},{"key":"e_1_2_1_11_1","volume-title":"Migrating and replicating data in networks. Computer Science\u2014Research and Development 27, 3","author":"Bienkowski Marcin","year":"2012","unstructured":"Marcin Bienkowski . 2012. Migrating and replicating data in networks. Computer Science\u2014Research and Development 27, 3 ( 2012 ), 169--179. Marcin Bienkowski. 2012. Migrating and replicating data in networks. Computer Science\u2014Research and Development 27, 3 (2012), 169--179."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.07.006"},{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","key":"e_1_2_1_14_1","unstructured":"Allan Borodin and Ran El-Yaniv . 1998. Online Computation and Competitive Analysis . Cambridge University Press . Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0853"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/75577.75583"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795287824"},{"volume-title":"Proc. 38th IEEE Symp. on Foundations of Computer Science (FOCS). 284--293","author":"Maggs Bruce M.","key":"e_1_2_1_19_1","unstructured":"Bruce M. Maggs , Friedhelm Meyer auf der Heide, Berthold V\u00f6cking, and Matthias Westermann. 1997. Exploiting locality for data management in systems of limited bandwidth . In Proc. 38th IEEE Symp. on Foundations of Computer Science (FOCS). 284--293 . Bruce M. Maggs, Friedhelm Meyer auf der Heide, Berthold V\u00f6cking, and Matthias Westermann. 1997. Exploiting locality for data management in systems of limited bandwidth. In Proc. 38th IEEE Symp. on Foundations of Computer Science (FOCS). 284--293."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_2_1_21_1","first-page":"161","article-title":"Uniform page migration on general networks","volume":"42","author":"Matsubayashi Akira","year":"2008","unstructured":"Akira Matsubayashi . 2008 . Uniform page migration on general networks . Int. J. Pure Appl. Math. 42 , 2 (2008), 161 -- 168 . Akira Matsubayashi. 2008. Uniform page migration on general networks. Int. J. Pure Appl. Math. 42, 2 (2008), 161--168.","journal-title":"Int. J. Pure Appl. Math."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CANDAR.2015.62"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9841-9"},{"key":"e_1_2_1_24_1","volume-title":"Uniform page migration problem in Euclidean space. Algorithms 9, 3","author":"Matsubayashi Akira","year":"2016","unstructured":"Akira Matsubayashi , Amanj Khorramian . 2016. Uniform page migration problem in Euclidean space. Algorithms 9, 3 ( 2016 ). Akira Matsubayashi, Amanj Khorramian. 2016. Uniform page migration problem in Euclidean space. Algorithms 9, 3 (2016)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"volume-title":"Proc. 7th European Symp. on Algorithms (ESA). 89--100","author":"Friedhelm","key":"e_1_2_1_26_1","unstructured":"Friedhelm Meyer auf der Heide, Berthold V\u00f6cking, and Matthias Westermann. 1999. Provably good and practical strategies for non-uniform data management in networks . In Proc. 7th European Symp. on Algorithms (ESA). 89--100 . Friedhelm Meyer auf der Heide, Berthold V\u00f6cking, and Matthias Westermann. 1999. Provably good and practical strategies for non-uniform data management in networks. In Proc. 7th European Symp. on Algorithms (ESA). 89--100."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791199796"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340296","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:32Z","timestamp":1750268972000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340296"}},"subtitle":["On Phase-based Algorithms for File Migration"],"short-title":[],"issued":{"date-parts":[[2019,7,25]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3340296"],"URL":"https:\/\/doi.org\/10.1145\/3340296","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,7,25]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}