City Research Online

Abstract

We study the problem of searching for a target at some unknown location in ℝ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 ∈ ℝ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 ℝd.

Publication Type:	Conference or Workshop Item (Paper)
Additional Information:	This version of the contribution has been accepted for publication, after peer review but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms
Publisher Keywords:	search games, predictions, Euclidean space
Subjects:	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