Online Searching with the Common Sources

We consider the problem of searching m branches which, with the exception of a common source s, are disjoint (hereafter called concurrent branches). A searcher, starting at s, must find a given “exit” t whose location, unknown to the searcher, is on one of the m branches. The problem is to find a strategy that minimizes the worst case ratio between the total distance traveled and the length of the shortest path from s to t. Additional information may be available to the searcher before he begins his search. In addition to finding optimal or near optimal deterministic online algorithms for these problems this paper addresses the “value” of getting additional information before starting the search.

Download PDF