The ultimate strategy to search on m rays?
Loading...
Files
Date
1998
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We consider the problem of searching on m current rays for a target of unknown location. If no upper bound on the distance to the target is known in advance, then the optimal competitive ratio is 1 + 2m[superscript m] / ( m - 1 )[superscript m-1]. We show that if an upper bound of D on the distance to the target is known in advance, then the competitive ratio of any search strategy is at least 1 + 2m[superscript m]/(m -1)[superscript m-1] - 0(1/log[superscript 2] D) which is also optimal-but in a stricter sense. We construct a search strategy that achieves this ratio. Our strategy works equally as well for the unbounded case, and produces a strategy where the point is found at a competitive distance of 1 + 2m[superscript m] f(m -1)[superscript m-1] - 0(1/log[superscript 2] D), for unknown, unbounded D, that is, it is not necessary for our strategy to know an upper bound on the distance D in advance.