Speaker: Spyros Angelopoulos CNRS, France
Title: On variants of online ray searching
We consider the problem of exploring a set of m concurrent rays using a single searcher. The rays are disjoint with the exception of a single common point, and in each ray a potential target may be located. The objective is to design efficient search strategies for locating the targets as quickly as possible.
In this talk I will describe results on two variants of this well-studied problem. In the first variant, the searcher must locate t targets (with t less than or equal to m ); this generalizes the setting in which only a single target is sought. The second variant corresponds to the setting in which the searcher incurs a fixed cost upon switching direction. For this problem, I will describe a proper use of infinite LP formulations that yields tight lower bounds.