2005
Bucket Game with Applications to Set Multicover and Dynamic Page Migration
Publication
Publication
Presented at the
European Symposium on Algorithms
We present a simple two-person Bucket Game, based on throwing balls into buckets, and we discuss possible players’ strategies. We use these strategies to create an approximation algorithm for a generalization of the well known Set Cover problem, where we need to cover each element by at least k sets. Furthermore, we apply these strategies to construct a randomized algorithm for Dynamic Page Migration problem achieving the optimal competitive ratio against an oblivious adversary.
| Additional Metadata | |
|---|---|
| Springer | |
| Lecture Notes in Computer Science | |
| European Symposium on Algorithms | |
| Organisation | Networks and Optimization |
|
Bienkowski, M., & Byrka, J. (2005). Bucket Game with Applications to Set Multicover and Dynamic Page Migration. In Proceedings of the 13th Annual European Symposium on Algorithms (pp. 815–826). Springer. |
|