|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Mutual Search | | Harry Buhrman
; Matthew Franklin
; Juan A. Garay
; Jaap-Henk Hoepman
; John Tromp
; Paul Vitanyi
; | | Date: |
2 Feb 1999 | | Subject: | Data Structures and Algorithms; Computational Complexity; Databases; Distributed, Parallel, and Cluster Computing; Discrete Mathematics; Information Retrieval ACM-class: F.2,C.2,E,1,D.4.4 | cs.DS cs.CC cs.DB cs.DC cs.DM cs.IR | | Affiliation: | CWI), Matthew Franklin (Xerox PARC), Juan A. Garay (Bell Labs - Lucent Technologies), Jaap-Henk Hoepman (University Twente), John Tromp (CWI), Paul Vitanyi (CWI and University of Amsterdam | | Abstract: | We introduce a search problem called ``mutual search’’ where $k$ agents, arbitrarily distributed over $n$ sites, are required to locate one another by posing queries of the form ``Anybody at site $i$?’’. We ask for the least number of queries that is necessary and sufficient. For the case of two agents using deterministic protocols we obtain the following worst-case results: In an oblivious setting (where all pre-planned queries are executed) there is no savings: $n-1$ queries are required and are sufficient. In a nonoblivious setting we can exploit the paradigm of ``no news is also news’’ to obtain significant savings: in the synchronous case $0.586n$ queries suffice and $0.536n$ queries are required; in the asynchronous case $0.896n$ queries suffice and a fortiori 0.536 queries are required; for $o(sqrt{n})$ agents using a deterministic protocol less than $n$ queries suffice; there is a simple randomized protocol for two agents with worst-case expected $0.5n$ queries and all randomized protocols require at least $0.125n$ worst-case expected queries. The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest. | | Source: | arXiv, cs.DS/9902005 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER