Wednesday 4th June 2014, 4.00pm, 32L LG.14
Spyros Angelopoulosk
University Pierre et Marie Curie, Paris
Personal profile
Abstract:
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.