  We study the classic problem in which a Searcher must locate a hidden point,
also called the Hider in a network, starting from a root point. The network may
be either bounded or unbounded, thus generalizing well-known settings such as
linear and star search. We distinguish between pathwise search, in which the
Searcher follows a continuous unit-speed path until the Hider is reached, and
expanding search, in which, at any point in time, the Searcher may restart from
any previously reached point. The former has been the usual paradigm for
studying search games, whereas the latter is a more recent paradigm that can
model real-life settings such as hunting for a fugitive, demining a field, or
search-and-rescue operations. We seek both deterministic and randomized search
strategies that minimize the competitive ratio, namely the worst-case ratio of
the Hider's discovery time, divided by the shortest path to it from the root.
Concerning expanding search, we show that a simple search strategy that applies
a "waterfilling" principle has optimal deterministic competitive ratio; in
contrast, we show that the optimal randomized competitive ratio is attained by
fairly complex strategies even in a very simple network of three arcs.
Motivated by this observation, we present and analyze an expanding search
strategy that is a 5/4 approximation of the randomized competitive ratio. Our
approach is also applicable to pathwise search, for which we give a strategy
that is a 5 approximation of the randomized competitive ratio, and which
improves upon strategies derived from previous work.
