Bucket game with applications to set multicover and dynamic page migration

M. Bienkowski; J. Byrka

doi:10.1007/11561071_72

Bucket game with applications to set multicover and dynamic page migration

M. Bienkowski
, J. Byrka

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

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.

Original language	English
Title of host publication	Algorithms - ESA 2005
Subtitle of host publication	13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings
Editors	Gerth Stølting Brodal, Stefano Leonardi
Place of Publication	Berlin
Publisher	Springer
Chapter	72
Pages	815-826
Number of pages	12
ISBN (Electronic)	978-3-540-31951-1
ISBN (Print)	3-540-29118-0, 978-3-540-29118-3
DOIs	https://doi.org/10.1007/11561071_72
Publication status	Published - 2005

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Volume	3669
ISSN (Print)	0302-9743

Access to Document

10.1007/11561071_72

Cite this

Bienkowski, M., & Byrka, J. (2005). Bucket game with applications to set multicover and dynamic page migration. In G. Stølting Brodal, & S. Leonardi (Eds.), Algorithms - ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings (pp. 815-826). (Lecture Notes in Computer Science (LNCS); Vol. 3669). Springer. https://doi.org/10.1007/11561071_72

@inproceedings{d6453bb8011f4308bf04f807cc74d813,

title = "Bucket game with applications to set multicover and dynamic page migration",

abstract = "We present a simple two-person Bucket Game, based on throwing balls into buckets, and we discuss possible players{\textquoteright} 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.",

author = "M. Bienkowski and J. Byrka",

year = "2005",

doi = "10.1007/11561071\_72",

language = "English",

isbn = "3-540-29118-0",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "815--826",

editor = "\{St{\o}lting Brodal\}, \{Gerth \} and Stefano Leonardi",

booktitle = "Algorithms - ESA 2005",

address = "Germany",

}

Bienkowski, M & Byrka, J 2005, Bucket game with applications to set multicover and dynamic page migration. in G Stølting Brodal & S Leonardi (eds), Algorithms - ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings. Lecture Notes in Computer Science (LNCS), vol. 3669, Springer, Berlin, pp. 815-826. https://doi.org/10.1007/11561071_72

Bucket game with applications to set multicover and dynamic page migration. / Bienkowski, M.; Byrka, J.
Algorithms - ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings. ed. / Gerth Stølting Brodal; Stefano Leonardi. Berlin: Springer, 2005. p. 815-826 (Lecture Notes in Computer Science (LNCS); Vol. 3669).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Bucket game with applications to set multicover and dynamic page migration

AU - Bienkowski, M.

AU - Byrka, J.

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1007/11561071_72

DO - 10.1007/11561071_72

M3 - Conference contribution

SN - 3-540-29118-0

SN - 978-3-540-29118-3

T3 - Lecture Notes in Computer Science (LNCS)

SP - 815

EP - 826

BT - Algorithms - ESA 2005

A2 - Stølting Brodal, Gerth

A2 - Leonardi, Stefano

PB - Springer

CY - Berlin

ER -

Bucket game with applications to set multicover and dynamic page migration

Abstract

Publication series

Access to Document

Fingerprint

Cite this