論文

査読有り
2016年8月23日

Uniform page migration problem in Euclidean space

Algorithms
  • Amanj Khorramian
  • ,
  • Akira Matsubayashi

9
3
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.3390/a9030057
出版者・発行元
MDPI AG

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.

リンク情報
DOI
https://doi.org/10.3390/a9030057
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000382510100015&DestApp=WOS_CPL
ID情報
  • DOI : 10.3390/a9030057
  • ISSN : 1999-4893
  • SCOPUS ID : 85024884166
  • Web of Science ID : WOS:000382510100015

エクスポート
BibTeX RIS