Bucket Game with Applications to Set Multicover and Dynamic Page Migration

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