Competitive search in a network
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- A general search game
- A Mixed-Strategy Minimax Theorem without Compactness
- Approximate solutions for expanding search games on general networks
- Competitive Online Approximation of the Optimal Search Ratio
- How to find a point on a line within a fixed distance
- scientific article; zbMATH DE number 1507215 (Why is no real title available?)
- scientific article; zbMATH DE number 2102754 (Why is no real title available?)
- scientific article; zbMATH DE number 3245077 (Why is no real title available?)
- Hyperbolic Dovetailing
- Infinite linear programming and online searching with turn cost
- Minimax Solutions for Linear Search Problems
- Mining coal or finding terrorists: the expanding search paradigm
- Multi-target ray searching problems
- On-line parallel heuristics, processor scheduling and robot searching under the competitive framework
- Online searching with turn cost
- Optimal Constructions of Hybrid Algorithms
- Search Games with Mobile and Immobile Hider
- Searching on a line: a complete characterization of the optimal solution
- The expanding search ratio of a graph
- The expanding search ratio of a graph
- The Oil Searching Problem
- The theory of search games and rendezvous.
- The ultimate strategy to search on \(m\) rays?
- Yet more on the linear search problem
Cited in
(18)- Flood search under the California split rule.
- On the approximation ratio of the random Chinese postman tour for network search
- The expanding search ratio of a graph
- A competitive search game with a moving target
- Online routing and searching on graphs with blocked edges
- Approximate solutions for expanding search games on general networks
- Search for an immobile hider in a known subset of a network
- The expanding search ratio of a graph
- Competition and networks of collaboration
- scientific article; zbMATH DE number 2102754 (Why is no real title available?)
- Exact and Approximation Algorithms for the Expanding Search Problem
- Competitive search in symmetric trees
- Mining coal or finding terrorists: the expanding search paradigm
- The faulty Satnav (GPS) problem: search for home in networks with unreliable directions
- Weighted online search
- Optimal linear tracking for a hidden target on one of \(K\)-intervals
- A study on the existence of a cooperative search method with reducing the first metting time between one of several nano-sensors and a Brownian particle
- Discrete search stability for a hidden target on M-intervals with a known probabilistic distributed effort
This page was built for publication: Competitive search in a network
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2184175)
