Utskrift från Malmö universitet - mau.se
Utskrift från Malmö universitet - mau.se
Publication | Article, peer reviewed scientific |
Title | Parallel Searching on m Rays |
Author | Hammar, Mikael ; Nilsson, Bengt J. ; Schuierer, Sven |
Date | 2001 |
English abstract | |
We investigate parallel searching on $m$ concurrent rays. We assume that a target $t$ is located somewhere on one of the rays; we are given a group of $m$ point robots each of which has to reach $t$. Furthermore, we assume that the robots have no way of communicating over distance. Given a strategy $S$ we are interested in the competitive ratio defined as the ratio of the time needed by the robots to reach $t$ using $S$ and the time needed to reach $t$ if the location of $t$ is known in advance. If a lower bound on the distance to the target is known, then there is a simple strategy which achieves a competitive ratio of~9 --- independent of $m$. We show that 9 is a lower bound on the competitive ratio for two large classes of strategies if $m\geq 2$. If the minimum distance to the target is not known in advance, we show a lower bound on the competitive ratio of $1 + 2 (k + 1)^{k + 1} / k^k$ where $k = \left\lceil\log m\right\rceil$ where $\log$ is used to denote the base 2 logarithm. We also give a strategy that obtains this ratio. | |
Publisher | Elsevier |
Host/Issue | Computational Geometry: Theory and Applications;3 |
Volume | 18 |
Pages | 125-139 |
Language | eng (iso) |
Subject | Computational Geometry Online Search Strategies Sciences Research Subject Categories::MATHEMATICS::Applied mathematics::Theoretical computer science |
Handle | http://hdl.handle.net/2043/6643 Permalink to this page |
Tweet |