Abstract
|
We explore the connections between search theory and machine scheduling by examining a little-known ordering problem proposed by N. Pisaruk (1992). A target is hidden in one of a finite number of locations S, which must be searched in some order. The cost of searching an initial segment A of a given ordering is f(A) and the probability the target is located in A is g(A), where f is a non-decreasing submodular function and g is a non-decreasing super modular function. We wish to find the ordering that discovers the target in minimal expected cost. The problem has applications to both machine scheduling and search theory, but is NP-hard. We present a new 2-approximation algorithm that generalizes well-known results in scheduling theory and establishes new ones. We also consider a version of the problem when nothing is known about the hiding probability, in which case we seek the randomized ordering that minimizes the expected cost in the worst case; equivalently this can be viewed as a zero-sum game. |