Bucket Game with Applications to Set Multicover and Dynamic Page Migration
M. Bienkowski, J. Byrka, in: Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005), Springer , Berlin, Heidelberg, 2005, pp. 815–826.
Download
No fulltext has been uploaded.
Conference Paper
| Published
| English
Author
Bienkowski, Marcin;
Byrka, Jarosław
Abstract
We present a simple two-person Bucket Game, based on throwing balls into buckets, and we<br>discuss possible players' strategies.<br><br>We use these strategies to create an approximation algorithm for a generalization of<br>the well known Set Cover problem, where we need to cover each element by at least $k$ sets.<br>Furthermore, we apply these strategies to construct a randomized algorithm for Dynamic Page Migration <br>problem achieving the optimal competitive ratio against an oblivious adversary.
Publishing Year
Proceedings Title
Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)
Volume
3669
Page
815-826
ISBN
LibreCat-ID
Cite this
Bienkowski M, Byrka J. Bucket Game with Applications to Set Multicover and Dynamic Page Migration. In: Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005). Vol 3669. Berlin, Heidelberg: Springer ; 2005:815-826. doi:10.1007/11561071_72
Bienkowski, M., & Byrka, J. (2005). Bucket Game with Applications to Set Multicover and Dynamic Page Migration. In Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005) (Vol. 3669, pp. 815–826). Berlin, Heidelberg: Springer . https://doi.org/10.1007/11561071_72
@inproceedings{Bienkowski_Byrka_2005, place={Berlin, Heidelberg}, title={Bucket Game with Applications to Set Multicover and Dynamic Page Migration}, volume={3669}, DOI={10.1007/11561071_72}, booktitle={Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)}, publisher={Springer }, author={Bienkowski, Marcin and Byrka, Jarosław}, year={2005}, pages={815–826} }
Bienkowski, Marcin, and Jarosław Byrka. “Bucket Game with Applications to Set Multicover and Dynamic Page Migration.” In Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005), 3669:815–26. Berlin, Heidelberg: Springer , 2005. https://doi.org/10.1007/11561071_72.
M. Bienkowski and J. Byrka, “Bucket Game with Applications to Set Multicover and Dynamic Page Migration,” in Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005), 2005, vol. 3669, pp. 815–826.
Bienkowski, Marcin, and Jarosław Byrka. “Bucket Game with Applications to Set Multicover and Dynamic Page Migration.” Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005), vol. 3669, Springer , 2005, pp. 815–26, doi:10.1007/11561071_72.
Google Scholar
ISBN Search