Randomised Mutual Search

J.H. Hoepman

    Research output: Working paper

    4 Downloads (Pure)

    Abstract

    We study the efficiency of randomised solutions to the mutual search problem of finding k agents distributed over n nodes. For a restricted class of so-called linear randomised mutual search algorithms we derive a lower bound of k−1 k+1 (n+1) expected calls in the worst case. A randomised algorithm in the shared-coins model matching this bound is also presented. Finally we show that in general more adaptive randomized mutual algorithms perform better (using k−1+k−1k+1− k−2n(n−k) worst case expected calls in the shared coins model) than the lower bound for the restricted case, even when given only private coins. A lower bound of k − 1 + n−k k+1 for this case is also derived.
    Original languageEnglish
    Place of PublicationEnschede
    PublisherUniversity of Twente
    Number of pages14
    Publication statusPublished - 10 Aug 2000

    Keywords

    • METIS-119095

    Cite this

    Hoepman, J. H. (2000). Randomised Mutual Search. Enschede: University of Twente.