AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

45 Minutes

Saarbrücken

We consider the problem of exploring m concurrent rays (i.e., branches)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 t targets (with t<= m). This setting generalizes the extensively studied ray search (or star search) problem, in which the searcher seeks a single target. In addition, it is motivated by applications such as the interleaved execution of heuristic algorithms, when it is required that a certain number of heuristics have to successfully terminate. We study the problem under two different cost measures, and show how to derive optimal search strategies for each measure.

Joint work with Konstantinos Panagiotou and Alex Lopez-Ortiz.

Spyros Angelopoulos

--email hidden

passcode not visible

logged in users only