{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:21:10Z","timestamp":1760242870424,"version":"build-2065373602"},"reference-count":12,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2016,8,23]],"date-time":"2016-08-23T00:00:00Z","timestamp":1471910400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"JSPS KAKENHI","award":["26330008"],"award-info":[{"award-number":["26330008"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The page migration problem in Euclidean space is revisited. In this problem, online requests occur at any location to access a single page located at a server. Every request must be served, and the server has the choice to migrate from its current location to a new location in space. Each service costs the Euclidean distance between the server and request. A migration costs the distance between the former and the new server location, multiplied by the page size. We study the problem in the uniform model, in which the page has size D = 1 . All request locations are not known in advance; however, they are sequentially presented in an online fashion. We design a 2.75 -competitive online algorithm that improves the current best upper bound for the problem with the unit page size. We also provide a lower bound of 2.732 for our algorithm. It was already known that 2.5 is a lower bound for this problem.<\/jats:p>","DOI":"10.3390\/a9030057","type":"journal-article","created":{"date-parts":[[2016,8,23]],"date-time":"2016-08-23T10:18:55Z","timestamp":1471947535000},"page":"57","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Uniform Page Migration Problem in Euclidean Space"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8382-7684","authenticated-orcid":false,"given":"Amanj","family":"Khorramian","sequence":"first","affiliation":[{"name":"Division of Electrical Engineering and Computer Science, Kanazawa University, Kanazawa 920-1192, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7861-4876","authenticated-orcid":false,"given":"Akira","family":"Matsubayashi","sequence":"additional","affiliation":[{"name":"Division of Electrical Engineering and Computer Science, Kanazawa University, Kanazawa 920-1192, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,8,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/s00450-011-0150-8","article-title":"Migrating and replicating data in networks","volume":"27","author":"Bienkowski","year":"2012","journal-title":"Comput. Sci.-Res. Dev."},{"key":"ref_2","unstructured":"Black, D.L., and Sleator, D.D. (1989). Competitive Algorithms for Replication and Migration Problems, Carnegie Mellon University. Technical Report CMU-CS-89-201."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1006\/jagm.1996.0853","article-title":"Page migration algorithms using work functions","volume":"24","author":"Chrobak","year":"1997","journal-title":"J. Algorithms."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"951","DOI":"10.1137\/S0097539791199796","article-title":"Randomized algorithms for multiprocessor page migration","volume":"23","author":"Westbrook","year":"1994","journal-title":"SIAM J. Comput."},{"key":"ref_5","first-page":"161","article-title":"Uniform page migration on general networks","volume":"42","author":"Matsubayashi","year":"2008","journal-title":"Int. J. Pure Appl. Math."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Meyer auf der Heide, F., V\u00f6cking, B., and Westermann, M. (1999, January 16\u201318). Provably Good and Practical Strategies for Non-Uniform Data Management in Networks. Proceedings of the 7th Annual European Symposium on Algorithms (LNCS 1643), Prague, Czech Republic.","DOI":"10.1007\/3-540-48481-7_9"},{"key":"ref_7","unstructured":"Maggs, B.M., Meyer auf der Heide, F., V\u00f6cking, B., and Westermann, M. (1997, January 19\u201322). Exploiting Locality for Data Management in Systems of Limited Bandwidth. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, USA."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0304-3975(00)00259-0","article-title":"On page migration and other relaxed task systems","volume":"268","author":"Bartal","year":"2001","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Matsubayashi, A. (2015, January 8\u201311). A 3+Omega (1) Lower Bound for Page Migration. Proceedings of the 2015 Third International Symposium on Computing and Networking, Sapporo, Japan.","DOI":"10.1109\/CANDAR.2015.62"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1007\/s00453-013-9841-9","article-title":"Asymptotically optimal online page migration on three points","volume":"71","author":"Matsubayashi","year":"2015","journal-title":"Algorithmica"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1006\/jcss.1995.1073","article-title":"Competitive algorithms for distributed data management","volume":"51","author":"Bartal","year":"1995","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1086","DOI":"10.1137\/S0097539795287824","article-title":"Competitive on-line algorithms for distributed data management","volume":"28","author":"Lund","year":"1999","journal-title":"SIAM J. Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/3\/57\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:29:01Z","timestamp":1760210941000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/3\/57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,23]]},"references-count":12,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2016,9]]}},"alternative-id":["a9030057"],"URL":"https:\/\/doi.org\/10.3390\/a9030057","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2016,8,23]]}}}