[{"language":[{"iso":"eng"}],"department":[{"_id":"63"}],"series_title":"Lecture Notes in Computer Science","user_id":"15415","_id":"18925","status":"public","abstract":[{"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.","lang":"eng"}],"publication":"Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS)","type":"conference","doi":"10.1007/978-3-540-31856-9_30","title":"Improved Algorithms for Dynamic Page Migration","author":[{"full_name":"Bienkowski, Marcin","last_name":"Bienkowski","first_name":"Marcin"},{"full_name":"Dynia, Miroslaw","last_name":"Dynia","first_name":"Miroslaw"},{"first_name":"Miroslaw","full_name":"Korzeniowski, Miroslaw","last_name":"Korzeniowski"}],"date_created":"2020-09-03T10:01:03Z","date_updated":"2022-01-06T06:53:54Z","page":"365-376","citation":{"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} }","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.","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>","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.","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>"},"year":"2005","publication_identifier":{"isbn":["9783540249986","9783540318569"],"issn":["0302-9743","1611-3349"]},"publication_status":"published"}]