New measures and algorithms for online searching

Context

Searching for a hidden target is a common task in everyday life and, unsurprisingly, a significant

computational problem with important applications. In this type of problems, we encounter a game

between a Searcher and a Hider, which is played within a given search environment (e.g., a network

represented by an undirected, edge-weighted graph). For the Hider, for whom a pure strategy is a

hiding point in the environment, whereas for the Searcher a pure strategy is some choice of how to

navigate through the environment. Such games are often analyzed by means of the competitive ratio:

namely, the worst-case ratio of the cost incurred by the search over the (optimum) cost assuming full

information of the location of the Hider. For this reason, search problems in theoretical computer science

fall typically within the domain of online computing.

A specific search environment that has attracted a lot of attention in previous research is the star-like

environment (with the corresponding search problem often referred to as star searching or ray searching).

Here, the environment consists of a set of finite or even infinite lines which have a common intersection

point (the root of the Searcher). Indeed star search has applications that are not necessarily confined to the

concept of locating a target (which explains its significance and popularity). This is because it offers an

abstraction that applies naturally in settings in which we seek an intelligent allocation of resources to tasks

(e.g., when the objective is to successfully complete at least one task, without knowing in advance the completion

time of each task). Such applications include drilling for oil in a number of locations or interleaving several

processes in a single-processor machine as efficiently as possible.

Objectives

In this topic, we are interesting in new measures for analyzing search problems, and in obtaining new efficient

algorithms for the introduced measures. For instance, for search problems which have been studied in Operations

Research as purely combinatorial optimization problems, we seek search strategies that optimize the competitive

ratio. As another concrete example, we study some recently introduced measures due to Kirkpatrick [ESA 2009]

and McGregor et al [ESA 2009] concerning star search. Here, we compare the cost of the online strategy to the cost

of an offline algorithm that has only partial information about the input instance. More precisely, the offline

algorithm may know the distance of a target (or targets) from the origin of the star graph, but not the exact mapping

of these distances to the actual "rays" of the star graph.

Results

1. Multitarget ray searching problems

(by Spyros Angelopoulos, Alejandro Lopez-Ortiz and Konstantinos Panagiotou)

In this work we study the problem of exploring m concurrent rays using a searcher. The rays are disjoint with

the exception of a single common point, and in each ray at most one potential target may be located. The objective

is to design search strategies for locating t targets among the m while minimizing the search distance traversed.

This setting generalizes the extensively studied the star search problem problem, in which the searcher seeks a single target.

We apply two different measures for evaluating the efficiency of the search strategy. The first measure is the

standard metric in the context of ray-search problems, and compares the total search cost to the cost of an optimal

algorithm that has full information on the targets. We present a simple strategy that achieves optimal competitive

ratio under this metric. Our main result pertains to the second measure, which is based on the weakening of the

optimal cost as proposed by Kirkpatrick [ESA 2009] and McGregor et al. [2009]. For this model, we present

an asymptotically optimal strategy that is within a multiplicative factor Θ(log (m-t)). Our results demonstrate

that, for both problems, the problem of locating $t$ targets in m rays is essentially as difficult as the problem

of locating a single target in m-(t-1) rays.

This work appeared in Theoretical Computer Science, 2014.

2. The expanding search ratio of a graph

(by Spyros Angelopoulos, Christoph Dürr and Thomas Lidbetter)

We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted

graph. Most of the previous work on this problem considers the pathwise cost formulation, in which

the cost incurred by the searcher is the overall time to locate the target, assuming that the searcher moves

at unit speed. More recent work introduced the setting of expanding search in which the searcher incurs cost

only upon visiting previously unexplored areas of the graph. Such a paradigm is useful in modeling problems

in which the cost of re-exploration is negligible (such as coal mining).

In our work we study algorithmic and computational issues of expanding search, for a variety of search

environments including general graphs, trees and star-like graphs. In particular, we rely on the deterministic

and randomized search ratio as the performance measures of search strategies, which were originally

introduced by Koutsoupias and Papadimitriou [ICALP 1996] in the context of pathwise search. The search ratio

is essentially the best competitive ratio among all possible strategies. Our main objective is to explore how

the transition from pathwise to expanding search affects the competitive analysis, which has applications

to optimization problems beyond the strict boundaries of search problems.

Paper will appear in the Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS), 2016.