The Library
Searching a variable speed network
Tools
Tools
Tools
Alpern, Steve and Lidbetter, Thomas (2014) Searching a variable speed network. Mathematics of Operations Research, Volume 39 (Number 3). pp. 697-711. doi:10.1287/moor.2013.0634 ISSN 0364-765X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1287/moor.2013.0634
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.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||||
| Journal or Publication Title: | Mathematics of Operations Research | ||||||
| Publisher: | Informs | ||||||
| ISSN: | 0364-765X | ||||||
| Official Date: | 23 December 2014 | ||||||
| Dates: |
|
||||||
| Volume: | Volume 39 | ||||||
| Number: | Number 3 | ||||||
| Page Range: | pp. 697-711 | ||||||
| DOI: | 10.1287/moor.2013.0634 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
