City Research Online

Abstract

We study the problem of searching for a target at some unknown location in R d when additional information regarding the position of the target is available in the form of predictions. In our setting, predictions come as approximate distances to the target: for each point p ∈ R d that the searcher visits, we obtain a value λ(p) such that |pt| ≤ λ(p) ≤ c · |pt|, where c ≥ 1 is a fixed constant, t is the position of the target, and |pt| is the Euclidean distance of p to t. The cost of the search is the length of the path followed by the searcher. Our main positive result is a strategy that achieves (12c) d+1-competitive ratio, even when the constant c is unknown. We also give a lower bound of roughly (c/16)d−1 on the competitive ratio of any search strategy in Rd.

Publication Type:	Other (Preprint)
Publisher Keywords:	search games, predictions, distance, computational geometry
Subjects:	G Geography. Anthropology. Recreation > GA Mathematical geography. Cartography Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments:	School of Science & Technology School of Science & Technology > Computer Science School of Science & Technology > Computer Science > giCentre
SWORD Depositor:	Symplectic Administrator

Export

Downloads