The ultimate strategy to search on m rays?
| dc.contributor.author | Lopez-Ortiz, Alejandro | |
| dc.contributor.author | Schuierer, Sven | |
| dc.date.accessioned | 2023-03-01T18:27:58Z | |
| dc.date.available | 2023-03-01T18:27:58Z | |
| dc.date.issued | 1998 | |
| dc.description.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. | |
| dc.description.copyright | Copyright @ Alejandro Lopez-Ortiz and Sven Schuierer, 1998. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14802 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | The ultimate strategy to search on m rays? | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1