Computer Science – Data Structures and Algorithms
Scientific paper
2004-06-23
Computer Science
Data Structures and Algorithms
15 pages, 2 figures, 1 table; to appear in Theoretical Computer Science. Did some minor editorial changes, fixed some typos, e
Scientific paper
We consider the problem of searching for an object on a line at an unknown distance OPT from the original position of the searcher, in the presence of a cost of d for each time the searcher changes direction. This is a generalization of the well-studied linear-search problem. We describe a strategy that is guaranteed to find the object at a cost of at most 9*OPT + 2d, which has the optimal competitive ratio 9 with respect to OPT plus the minimum corresponding additive term. Our argument for upper and lower bound uses an infinite linear program, which we solve by experimental solution of an infinite series of approximating finite linear programs, estimating the limits, and solving the resulting recurrences. We feel that this technique is interesting in its own right and should help solve other searching problems. In particular, we consider the star search or cow-path problem with turn cost, where the hidden object is placed on one of m rays emanating from the original position of the searcher. For this problem we give a tight bound of (1+(2(m^m)/((m-1)^(m-1))) OPT + m ((m/(m-1))^(m-1) - 1) d. We also discuss tradeoff between the corresponding coefficients, and briefly consider randomized strategies on the line.
Demaine Erik D.
Fekete Sandor P.
Gal Shmuel
No associations
LandOfFree
Online Searching with Turn Cost does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Online Searching with Turn Cost, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Searching with Turn Cost will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-247539