Bucket game with applications to set multicover and dynamic page migration

M. Bienkowski, J. Byrka

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
    Title of host publicationAlgorithms - ESA 2005
    Subtitle of host publication13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings
    EditorsGerth Stølting Brodal, Stefano Leonardi
    Place of PublicationBerlin
    PublisherSpringer
    Chapter72
    Pages815-826
    Number of pages12
    ISBN (Electronic)978-3-540-31951-1
    ISBN (Print)3-540-29118-0, 978-3-540-29118-3
    DOIs
    Publication statusPublished - 2005

    Publication series

    NameLecture Notes in Computer Science (LNCS)
    Volume3669
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'Bucket game with applications to set multicover and dynamic page migration'. Together they form a unique fingerprint.

    Cite this