Searching in Euclidean Spaces with Predictions.

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 | p t | ≤ λ ( p ) ≤ c · | p t | , where c ≥ 1 is a fixed constant, t is the position of the target, and | p t | 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 O ( c d ) -competitive ratio, even when the constant c is unknown. We also give a lower bound of roughly ( c / 4 ) d - 1 on the competitive ratio of any search strategy in R d , assuming that c ≥ 4 .