---
_id: '18925'
abstract:
- lang: eng
  text: 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:
- first_name: Marcin
  full_name: Bienkowski, Marcin
  last_name: Bienkowski
- first_name: Miroslaw
  full_name: Dynia, Miroslaw
  last_name: Dynia
- first_name: Miroslaw
  full_name: Korzeniowski, Miroslaw
  last_name: Korzeniowski
citation:
  ama: 'Bienkowski M, Dynia M, Korzeniowski M. Improved Algorithms for Dynamic Page
    Migration. In: <i>Proc. of the 22nd Symposium on Theoretical Aspects of Computer
    Science (STACS)</i>. Lecture Notes in Computer Science. ; 2005:365-376. doi:<a
    href="https://doi.org/10.1007/978-3-540-31856-9_30">10.1007/978-3-540-31856-9_30</a>'
  apa: Bienkowski, M., Dynia, M., &#38; Korzeniowski, M. (2005). Improved Algorithms
    for Dynamic Page Migration. In <i>Proc. of the 22nd Symposium on Theoretical Aspects
    of Computer Science (STACS)</i> (pp. 365–376). <a href="https://doi.org/10.1007/978-3-540-31856-9_30">https://doi.org/10.1007/978-3-540-31856-9_30</a>
  bibtex: '@inproceedings{Bienkowski_Dynia_Korzeniowski_2005, series={Lecture Notes
    in Computer Science}, title={Improved Algorithms for Dynamic Page Migration},
    DOI={<a href="https://doi.org/10.1007/978-3-540-31856-9_30">10.1007/978-3-540-31856-9_30</a>},
    booktitle={Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science
    (STACS)}, author={Bienkowski, Marcin and Dynia, Miroslaw and Korzeniowski, Miroslaw},
    year={2005}, pages={365–376}, collection={Lecture Notes in Computer Science} }'
  chicago: Bienkowski, Marcin, Miroslaw Dynia, and Miroslaw Korzeniowski. “Improved
    Algorithms for Dynamic Page Migration.” In <i>Proc. of the 22nd Symposium on Theoretical
    Aspects of Computer Science (STACS)</i>, 365–76. Lecture Notes in Computer Science,
    2005. <a href="https://doi.org/10.1007/978-3-540-31856-9_30">https://doi.org/10.1007/978-3-540-31856-9_30</a>.
  ieee: M. Bienkowski, M. Dynia, and M. Korzeniowski, “Improved Algorithms for Dynamic
    Page Migration,” in <i>Proc. of the 22nd Symposium on Theoretical Aspects of Computer
    Science (STACS)</i>, 2005, pp. 365–376.
  mla: Bienkowski, Marcin, et al. “Improved Algorithms for Dynamic Page Migration.”
    <i>Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS)</i>,
    2005, pp. 365–76, doi:<a href="https://doi.org/10.1007/978-3-540-31856-9_30">10.1007/978-3-540-31856-9_30</a>.
  short: 'M. Bienkowski, M. Dynia, M. Korzeniowski, in: Proc. of the 22nd Symposium
    on Theoretical Aspects of Computer Science (STACS), 2005, pp. 365–376.'
date_created: 2020-09-03T10:01:03Z
date_updated: 2022-01-06T06:53:54Z
department:
- _id: '63'
doi: 10.1007/978-3-540-31856-9_30
language:
- iso: eng
page: 365-376
publication: Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science
  (STACS)
publication_identifier:
  isbn:
  - '9783540249986'
  - '9783540318569'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
series_title: Lecture Notes in Computer Science
status: public
title: Improved Algorithms for Dynamic Page Migration
type: conference
user_id: '15415'
year: '2005'
...