A general framework for searching on a line

Consider the following classical search problem: a target is located on a line at distance from the origin. Starting at the origin, a searcher must find the target with minimum competitive cost. The classical competitive cost studied in the literature is the ratio between the distance travelled by the searcher and . Note that when no lower bound on is given, no competitive search strategy exists for this problem. Therefore, all competitive search strategies require some form of lower bound on .We develop a general framework that optimally solves several variants of this search problem. Our framework allows us to achieve optimal competitive search costs for previously studied variants such as: (1) where the target is fixed and the searcher's cost at each step is a constant times the length of the step, (2) where the target is fixed and the searcher's cost at each step is the length of the step plus a fixed constant (often referred to as the ), (3) where the target is moving and the searcher's cost at each step is the length of the step.Our main contribution is that the framework allows us to derive optimal competitive search strategies for variants of this problem that do not have a solution in the literature such as: (1) where the target is fixed and the searcher's cost at each step is for moving distance away from the origin and for moving back with constants , (2) where the target is moving and the searcher's cost at each step is a constant times the length of the step plus a fixed constant turn cost. Notice that the latter variant can have several interpretations depending on what the turn cost represents. For example, if the turn cost represents the amount of time for the searcher to turn, then this has an impact on the position of the moving target. On the other hand, the turn cost can represent the amount of fuel needed to make an instantaneous turn, thereby not affecting the target's position. Our framework addresses all of these variations.