Panos Giannopoulos: Searching in $R^d$ with predictions

Searching in $R^d$ with predictions

Panos Giannopoulos

Abstract: Searching for a target positioned at some unknown location in some region is a classic search game problem that has been well-studied in both fields of Computational Geometry and Operations Research. In this talk, we will consider the problem of searching for a target point in $R^d$ when additional information regarding the position of the target is available in the form of $c$-predictions – approximate distances to the target $t$: for each point $p$ that the searcher visits, a value $\lambda(p)$ is obtained such that $|pt| <= \lambda(p) <= c |pt|$, according to some unknown function $\lambda$ and where $c$ is a fixed (possibly unknown) constant.

I will show some simple search strategies that achieve constant competitive ratio (i.e., length of the path produced over the Euclidean distance of the target from the origin) as a function of $c$ and $d$. The strategies use metric $\epsilon$-nets and simple exponential search and work even if $c$ is unknown.

We will also see a lower bound of the competitive ratio of any deterministic search strategy in $R^d$ with $c$-predictions. This bound uses again $\epsilon$-nets and some techniques for Euclidean TSP with Neighborhoods.

(This is joint work with S. Cabello)