Home > Research > Publications & Outputs > Fast or Slow

Electronic data

  • Two Speed Search

    Rights statement: Copyright 2019 INFORMS

    Accepted author manuscript, 474 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

View graph of relations

Fast or Slow: Search in Discrete Locations with Two Search Modes

Research output: Contribution to journalJournal article

Forthcoming

Standard

Fast or Slow : Search in Discrete Locations with Two Search Modes. / Clarkson, Jake; Glazebrook, Kevin David; Lin, Kyle .

In: Operations Research, 08.03.2019.

Research output: Contribution to journalJournal article

Harvard

APA

Vancouver

Author

Bibtex

@article{b295172ed0c84224bb567263edc907f4,
title = "Fast or Slow: Search in Discrete Locations with Two Search Modes",
abstract = "An object is hidden in one of several discrete locations according to some known probability distribution, and the goal is to discover the object in minimum expected time by successive searches of individual locations. If there is only one way to search each location, this search problem is solved using Gittins indices. Motivated by modern search technology, we extend earlier work to allow two modes—fast and slow—to search each location. The fast mode takes less time, but the slow mode is more likely to find the object. An optimal policy is difficult to obtain in general, because it requires an optimal sequence of search modes for each location, in addition to a set of sequence-dependent Gittins indices for choosing between locations. Our analysis begins by—for each mode—identifying a sufficient condition for a location to use only that search mode in an optimal policy. For locations meeting neither sufficient condition, an optimal choice of search mode is extremely complicated, depending both on the probabilitydistribution of the object’s hiding location and the search parameters of the other locations. We propose several heuristic policies motivated by our analysis, and demonstrate their near-optimal performance in an extensive numerical study.",
author = "Jake Clarkson and Glazebrook, {Kevin David} and Kyle Lin",
note = "Copyright 2019 INFORMS",
year = "2019",
month = "3",
day = "8",
language = "English",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

}

RIS

TY - JOUR

T1 - Fast or Slow

T2 - Search in Discrete Locations with Two Search Modes

AU - Clarkson, Jake

AU - Glazebrook, Kevin David

AU - Lin, Kyle

N1 - Copyright 2019 INFORMS

PY - 2019/3/8

Y1 - 2019/3/8

N2 - An object is hidden in one of several discrete locations according to some known probability distribution, and the goal is to discover the object in minimum expected time by successive searches of individual locations. If there is only one way to search each location, this search problem is solved using Gittins indices. Motivated by modern search technology, we extend earlier work to allow two modes—fast and slow—to search each location. The fast mode takes less time, but the slow mode is more likely to find the object. An optimal policy is difficult to obtain in general, because it requires an optimal sequence of search modes for each location, in addition to a set of sequence-dependent Gittins indices for choosing between locations. Our analysis begins by—for each mode—identifying a sufficient condition for a location to use only that search mode in an optimal policy. For locations meeting neither sufficient condition, an optimal choice of search mode is extremely complicated, depending both on the probabilitydistribution of the object’s hiding location and the search parameters of the other locations. We propose several heuristic policies motivated by our analysis, and demonstrate their near-optimal performance in an extensive numerical study.

AB - An object is hidden in one of several discrete locations according to some known probability distribution, and the goal is to discover the object in minimum expected time by successive searches of individual locations. If there is only one way to search each location, this search problem is solved using Gittins indices. Motivated by modern search technology, we extend earlier work to allow two modes—fast and slow—to search each location. The fast mode takes less time, but the slow mode is more likely to find the object. An optimal policy is difficult to obtain in general, because it requires an optimal sequence of search modes for each location, in addition to a set of sequence-dependent Gittins indices for choosing between locations. Our analysis begins by—for each mode—identifying a sufficient condition for a location to use only that search mode in an optimal policy. For locations meeting neither sufficient condition, an optimal choice of search mode is extremely complicated, depending both on the probabilitydistribution of the object’s hiding location and the search parameters of the other locations. We propose several heuristic policies motivated by our analysis, and demonstrate their near-optimal performance in an extensive numerical study.

M3 - Journal article

JO - Operations Research

JF - Operations Research

SN - 0030-364X

ER -