Searching a variable speed network

Steve Alpern, Thomas Lidbetter

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

A point lies on a network according to some unknown probability distribution. Starting at a specified root of the network, a Searcher moves to find this point at speeds that depend on his location and direction. He seeks the randomized search algorithm that minimizes the expected search time. This is equivalent to modeling the problem as a zero-sum hide-and-seek game whose value is called the search value of the network. We make a new and direct derivation of an explicit formula for the search value of a tree, proving that it is equal to half the sum of the minimum tour time of the tree and a quantity called its incline. The incline of a tree is an average over the leaf nodes of the difference between the time taken to travel from the root to a leaf node and the time taken to travel from a leaf node to the root. This difference can be interpreted as height of a leaf node, assuming uphill is slower than downhill. We then apply this formula to obtain numerous results for general networks. We also introduce a new general method of comparing the search value of networks that differ in a single arc. Some simple networks have very complicated optimal strategies that require mixing of a continuum of pure strategies. Many of our results generalize analogous ones obtained for constant velocity (in both directions) by S. Gal, but not all of those results can be extended.

Original languageEnglish (US)
Pages (from-to)697-711
Number of pages15
JournalMathematics of Operations Research
Volume39
Issue number3
DOIs
StatePublished - Aug 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • Game
  • Immobile hider
  • Minimax
  • Network
  • Search
  • Search game

Fingerprint

Dive into the research topics of 'Searching a variable speed network'. Together they form a unique fingerprint.

Cite this