@inproceedings{18925,
  abstract     = {{The dynamic page migration problem citedynamic-page-migration is defined in <br>a distributed network of $n$ mobile nodes sharing one indivisible memory page <br>of size $D$. During runtime, the nodes can both access a unit of data from<br>the page and move with a constant speed, thus changing the costs of communication.<br>The problem is to compute <em> online</em> a schedule of page movements<br>to minimize the total communication cost.<br><br>In this paper we construct and analyze the first deterministic algorithm for this problem. <br>We prove that it achieves an (up to a constant factor) optimal competitive ratio <br>$O(n cdot sqrtD)$. We show that the randomization of this algorithm <br>improves this ratio to $O(sqrtD cdot log n)$ (against an oblivious adversary). <br>This substantially improves an $O(n cdot sqrtD)$ upper bound from citedynamic-page-migration.<br>We also give an almost matching lower bound of $Omega(sqrtD cdot sqrtlog n)$ for this problem.}},
  author       = {{Bienkowski, Marcin and Dynia, Miroslaw and Korzeniowski, Miroslaw}},
  booktitle    = {{Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS)}},
  isbn         = {{9783540249986}},
  issn         = {{0302-9743}},
  pages        = {{365--376}},
  title        = {{{Improved Algorithms for Dynamic Page Migration}}},
  doi          = {{10.1007/978-3-540-31856-9_30}},
  year         = {{2005}},
}