# Uniform Page Migration Problem in Euclidean Space
## 1 Introduction  
The page migration problem is a classical formulation of efficient memory management in a shared memory multiprocessor system comprising a network of processors having their own local memories. In this problem, we are given a sequence of requests issued by processors to access a single shared data object, called a page. Each request must be served via communication between the processor issuing the request and the processor holding the page at the time of the request. The service for the request costs the distance of the communication. After each service, the page is allowed to migrate from the current processor to a new processor before the next request is issued. The migration of the page costs the distance of the migration multiplied by the page size. The objective of the page migration problem is to minimize the total costs of services and migrations (see Section 2 for a formal definition of this problem). This problem can also be viewed as a formulation of general situations for managing shared information in a distributed network, such as the efficient allocation of each shared data object to be accessed by a distributed program running on the network [1]. [PERSON] and [PERSON] [2] first studied online algorithms for the page migration problem via competitive analysis. Some basic notions of competitive analysis are given in Section 2. [PERSON], [PERSON], [PERSON], and [PERSON] [3] studied this problem on continuous metric spaces as well as networks. They proposed a \((2+1/2D)\)-competitive randomized algorithm on trees against oblivious adversaries, together with the same lower bound as this competitiveness even at two points, where \(D\) is a positive integer representing the page size. They also proved that any randomized page migration algorithm on \(\mathbb{R}^{n}\) can be derandomized while preserving its competitiveness. As any page migration algorithm on a space can be generalized on Cartesian products of the space [2], a \((2+1/2D)\)-competitive deterministic algorithm on \(\mathbb{R}^{n}\) under \(L^{1}\) norm can be obtained through generalizing the algorithm on trees in \(\mathbb{R}^{n}\)[3]. For general metric spaces, [PERSON] [4] proposeda \(c\left(D\right)\)-competitive randomized algorithm against oblivious adversaries, where \(c\left(D\right)\) is a function defined in [4] that tends toward 2.618 as \(D\) grows large. Derandomizing this algorithm on \(\mathbb{R}^{n}\), we have a \(c\left(D\right)\)-competitive deterministic algorithm on \(\mathbb{R}^{n}\) under any norm [3]. Moreover, \(2+1/2D\) is a lower bound for any randomized or deterministic algorithm in the interval \(\left[0,\,1\right]\)[3]. This lower bound is also admitted on \(\mathbb{R}^{n}\) under \(L^{p}\) norm. This is because, for the interval \(I=\left[0,\,1\right]\) on a dimension \(k\) in \(\mathbb{R}^{n}\), any online algorithm \(A\) locating its server in \(\mathbb{R}^{n}\smallsetminus I\) for requests only in \(I\) has a cost of at least that of a certain algorithm locating its server only in \(I\), i.e., projection on the \(k\)th coordinate of \(A\)'s server location if the projection is in \(I\), and the closer endpoint of \(I\) otherwise. It is a longstanding open question whether we can close the gap of \(c\left(D\right)\) and \(2\ +\ 1/2D\) under \(L^{p}\) norm even with any \(p\geq 2\). In this paper, we partially answer this question by proposing a 2.75-competitive deterministic algorithm on \(\mathbb{R}^{n}\) under \(L^{2}\) norm for the case \(D=1\). We note that the competitiveness improves \(c\left(1\right)\), which is equal to 2.8 as mentioned in [4]. We also provide a lower bound of 2.732 for our algorithm. Our algorithm is extremely simple: it maintains the page at the center of two special points, both initially located at the initial location of the server. Upon each request, the algorithm chooses one of the points farther from the requested location and moves the point to the requested location; the other point does not move.