Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Mining coal or finding terrorists : the expanding search paradigm

Tools
- Tools
+ Tools

Alpern, Steve and Lidbetter, T. (2013) Mining coal or finding terrorists : the expanding search paradigm. Operations Research, 61 (2). pp. 265-279. doi:10.1287/opre.1120.1134

Full text not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1287/opre.1120.1134

Request Changes to record.

Abstract

We show how to optimize the search for a hidden object, terrorist, or simply Hider, located at a point H according to a known or unknown distribution ν on a rooted network Q. We modify the traditional “pathwise search” approach to a more general notion of “expanding search.” When the Hider is restricted to the nodes of Q, an expanding search S consists of an ordering Formula of the arcs of a spanning subtree such that the root node is in a1 and every arc ai is adjacent to a previous arc aj, j < i. If ak contains H, the search time T is Formula, where λ is length measure on Q. For more general distributions ν, an expanding search S is described by the nested family of connected sets S(t) that specify the area of Q that has been covered by time t. S(0) is the root, Formula. For a known Hider distribution ν on a tree Q, the expected time minimizing strategy Formula begins with the rooted subtree Q′ maximizing the “density” ν(Q′)/λ(Q′). (For arbitrary networks, we use this criterion on all spanning subtrees.) The search Formula can be interpreted as the optimal method of mining known coal seams, when the time to move miners or machines is negligible compared to digging time. When the Hider distribution is unknown, we consider the zero-sum search game where the Hider picks H, the Searcher S, and the payoff is T. For trees Q, the value is V = (λ(Q) + D)/2, where D is a mean distance from root to leaf nodes. If Q is 2-arc connected, V = λ(Q)/2. Applications and interpretations of the expanding search paradigm are given, particularly to multiple agent search.

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: Operations Research
Publisher: Institute for Operations Research and the Management Sciences (I N F O R M S)
ISSN: 0030-364X
Official Date: March 2013
Dates:
DateEvent
March 2013Published
Volume: 61
Number: 2
Page Range: pp. 265-279
DOI: 10.1287/opre.1120.1134
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 View Item
twitter

Email us: publications@live.warwick.ac.uk
Contact Details
About Us