Publikationen

Bienkowski, Marcin; Jaroslaw, Byrka: Bucket Game with Applications to Set Multicover and Dynamic Page Migration. In: Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005), LNCS, Band 3669 , S. 815-826, 3. - 6. Okt. 2005, Springer Verlag

Abstract

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.

Dateien

paper.pdf

Bibtex

@inproceedings{hniid=2456,
author = {Bienkowski, Marcin and Jaroslaw, Byrka},
title = {Bucket Game with Applications to Set Multicover and Dynamic Page Migration},
booktitle = {Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)},
volume = {3669},
series = {LNCS},
pages = {815-826},
publisher = {Springer Verlag},
month = {3~-~6~} # oct,
year = {2005},
}