The Revenge of the Linear Search Problem
Anatole Beck, Micah D. Beck · SIAM Journal on Control and Optimization · 1992
The linear search problem is the name for several problems motivated by the same external reality. At times, the search for a goal can proceed in two (or more) directions. Looking in one direction is at the expense of time and effort, which can be used elsewhere. More specifically, it might actually be moving further from the goal. This is modeled by a physical search along an infinite straight line, where the object of the search might be in either direction. Faced with a (known or unknown) probability distribution, this paper attempts to minimize the expected loss, where the loss is a function of the time of the search and the location of the object. In this variant of the problem, known distributions are dealt with, and the loss function is a known power of the time spent.