TY - JOUR

T1 - The expanding search ratio of a graph

AU - Angelopoulos, Spyros

AU - Dürr, Christoph

AU - Lidbetter, Thomas

N1 - Funding Information: Research supported in part by project ANR-11-BS02-0015, France “New Techniques in Online Computation—NeTOC”, and by the FMJH program Gaspard Monge in optimization and operations research, France and by EDF. Publisher Copyright: © 2019 Elsevier B.V.

PY - 2019/5/15

Y1 - 2019/5/15

N2 - We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. A sequence of edges is chosen starting from a given root vertex such that each edge is adjacent to a previously chosen edge. This search paradigm, known as expanding search was recently introduced by Alpern and Lidbetter (2013) for modeling problems such as searching for coal or minesweeping in which the cost of re-exploration is negligible. It can also be used to model a team of searchers successively splitting up in the search for a hidden adversary or explosive device, for example. We define the search ratio of an expanding search as the maximum over all vertices of the ratio of the time taken to reach the vertex and the shortest-path cost to it from the root. This can be interpreted as a measure of the multiplicative regret incurred in searching, and similar objectives have previously been studied in the context of conventional (pathwise) search. In this paper we address algorithmic and computational issues of minimizing the search ratio over all expanding searches, for a variety of search environments, including general graphs, trees and star-like graphs. Our main results focus on the problem of finding the randomized expanding search with minimum expected search ratio, which is equivalent to solving a zero-sum game between a Searcher and a Hider. We solve these problems for certain classes of graphs, and obtain constant-factor approximations for others.

AB - We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. A sequence of edges is chosen starting from a given root vertex such that each edge is adjacent to a previously chosen edge. This search paradigm, known as expanding search was recently introduced by Alpern and Lidbetter (2013) for modeling problems such as searching for coal or minesweeping in which the cost of re-exploration is negligible. It can also be used to model a team of searchers successively splitting up in the search for a hidden adversary or explosive device, for example. We define the search ratio of an expanding search as the maximum over all vertices of the ratio of the time taken to reach the vertex and the shortest-path cost to it from the root. This can be interpreted as a measure of the multiplicative regret incurred in searching, and similar objectives have previously been studied in the context of conventional (pathwise) search. In this paper we address algorithmic and computational issues of minimizing the search ratio over all expanding searches, for a variety of search environments, including general graphs, trees and star-like graphs. Our main results focus on the problem of finding the randomized expanding search with minimum expected search ratio, which is equivalent to solving a zero-sum game between a Searcher and a Hider. We solve these problems for certain classes of graphs, and obtain constant-factor approximations for others.

KW - Competitive analysis

KW - Game theory

KW - Graph search

KW - Randomized algorithms

KW - Search games

UR - http://www.scopus.com/inward/record.url?scp=85061976501&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85061976501&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/j.dam.2019.01.039

DO - https://doi.org/10.1016/j.dam.2019.01.039

M3 - Article

SN - 0166-218X

VL - 260

SP - 51

EP - 65

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -