Submodular Search and Machine Scheduling

Speaker: Thomas Lidbetter, Rutgers Business School

Abstract:
We consider 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 supermodular 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 the concept of a Sidney decomposition for single-machine scheduling in a natural way.  We improve the 2-approximation for submodular functions of low total curvature (roughly, the extent to which they differ from modular functions).  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.

Bio:
Thomas Lidbetter recently began a post as assistant professor at Rutgers Business School, after having worked as a postdoc at the London School of Economics (LSE) for the previous three years.  He also completed his PhD in mathematics at the LSE under the supervision of Steve Alpern, and his research interests are mainly in game theory and search theory, with applications to national security.