Randomised Mutual Search

J.H. Hoepman

Research output: Working paperProfessional

2 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.
Hoepman, J.H. / Randomised Mutual Search. Enschede : University of Twente, 2000.
@techreport{b35b38e69800481ca96a736dd9c10dbe,
title = "Randomised Mutual Search",
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.",
keywords = "METIS-119095",
author = "J.H. Hoepman",
year = "2000",
month = "8",
day = "10",
language = "English",
publisher = "University of Twente",
address = "Netherlands",
type = "WorkingPaper",
institution = "University of Twente",

}

Hoepman, JH 2000 'Randomised Mutual Search' University of Twente, Enschede.

Randomised Mutual Search. / Hoepman, J.H.

Enschede : University of Twente, 2000.

Research output: Working paperProfessional

TY - UNPB

T1 - Randomised Mutual Search

AU - Hoepman, J.H.

PY - 2000/8/10

Y1 - 2000/8/10

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

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

KW - METIS-119095

M3 - Working paper

BT - Randomised Mutual Search

PB - University of Twente

CY - Enschede

ER -

Hoepman JH. Randomised Mutual Search. Enschede: University of Twente. 2000 Aug 10.