Uniform page migration problem in Euclidean space
Summary: 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.
- A \(3 + \Omega (1)\) lower bound for page migration
- Asymptotically optimal online page migration on three points
- Competitive algorithms for distributed data management.
- Competitive On-Line Algorithms for Distributed Data Management
- scientific article; zbMATH DE number 5257110 (Why is no real title available?)
- On page migration and other relaxed task systems
- Page Migration Algorithms Using Work Functions
This page was built for publication: Uniform page migration problem in Euclidean space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736826)
