On Submodular Search and Machine Scheduling

Robbert Fokkink, Thomas Lidbetter, László A. Végh

Abstract

This paper investigates the Submodular Search Problem (SSP), a generalization of classic search and scheduling problems where costs and probabilities exhibit non-linear behaviors—specifically submodular costs and supermodular weights. The authors bridge search theory and combinatorial optimization to provide a robust 2-approximation algorithm and characterize equilibrium strategies for zero-sum search games using the geometric properties of submodular functions.

Introduction

In classical search theory, the problem of finding hidden objects with minimal expected cost is often solved using "Smith’s Rule," which dictates searching locations in decreasing order of their probability-to-cost ratio. However, real-world scenarios frequently involve complex dependencies. Costs may exhibit "diminishing returns" (submodularity), where searching adjacent areas is cheaper than the sum of searching them independently. Conversely, the probability of finding all objects might increase more than linearly as coverage expands (supermodularity).

This paper addresses the Submodular Search Problem (SSP), which seeks an optimal sequence of locations to minimize expected cost under these non-linear constraints. Given that the SSP is NP-hard, the research focuses on efficient approximation algorithms and game-theoretic extensions where a "Hider" actively attempts to maximize the searcher's expected cost.

Algorithmic Framework and Methodology

The authors generalize the Sidney decomposition, a classic technique in machine scheduling, to accommodate submodular structures. Their methodology is built upon several technical pillars:

  1. Search Density: The density of a set is defined as the ratio of its weight (probability) to its cost. This serves as the primary metric for prioritization.
  2. Maximum Density First: The core algorithm iteratively identifies a subset with the maximum search density, schedules it, and then "contracts" the problem by repeating the process on the remaining locations.
  3. Curvature Analysis: To refine approximation bounds, the authors utilize the concept of "total curvature" ($\kappa$). This metric quantifies how much a submodular function deviates from a simple linear sum, allowing for tighter performance guarantees.
  4. Polyhedral Combinatorics: For the game-theoretic analysis, the authors employ the base polyhedron—a geometric representation of a submodular function—to describe the optimal distribution of hiding probabilities for a rational Hider.

Key Insights

Generalizing Smith's Rule

A significant contribution of this work is demonstrating that the intuition behind simple scheduling (Smith's Rule) remains valid in the submodular regime. By applying the Sidney decomposition, any search sequence that respects the maximum density structure is guaranteed to be a 2-approximation of the optimal search.

The Hider’s Geometry

In the "Submodular Search Game," the authors prove that the Hider's optimal mixed strategy must lie within the scaled base polyhedron of the cost function. This establishes a rigorous geometric link between game theory and submodular optimization, providing a framework for analyzing adversarial search scenarios.

Series-Parallel Decomposability

The authors identify series-parallel decomposability as a critical structural property. While the general SSP is NP-hard, problems exhibiting this property can be solved exactly in polynomial time. This result generalizes previous findings that were limited to tree-structured search spaces.

Concave Scheduling and Learning Effects

The framework extends to a new class of scheduling problems ($1|prec|\sum w_A h(C_A)$) where the objective is to minimize a concave function of completion times. This effectively models "learning effects," where a machine's efficiency increases over time as it processes more tasks.

Results and Performance Bounds

  • 2-Approximation Guarantee: The proposed combinatorial algorithm is guaranteed to find a solution within a factor of 2 of the optimum for any submodular search problem.
  • Refined Curvature Bounds: For functions with low total curvature, the approximation ratio is improved to $2/(1+\delta)$, where $\delta$ is derived from the function's curvature.
  • Game Equilibrium: The research successfully characterizes the value and equilibrium strategies for the zero-sum search game, specifically providing solutions for the series-parallel decomposable case.
  • Polynomial Time Decidability: The authors provide a strongly polynomial-time algorithm to determine if a problem is series-parallel decomposable and, if so, to compute the optimal search sequence.

Limitations and Future Directions

While the paper provides a comprehensive characterization of equilibrium strategies, the exact computational complexity of finding these strategies in general (non-decomposable) games remains an open question. Additionally, there is a theoretical gap between the $2/(1+\delta)$ ratio and the potential $2/(1+\theta)$ ratio for general submodular functions, which remains a challenge for future research.

Future work may also explore multi-agent systems, including scenarios with multiple searchers (multi-machine scheduling) or "selfish" hiders who do not follow a zero-sum objective. Finally, developing a "distance" measure from series-parallel decomposability could lead to improved approximations for nearly-decomposable problems.

Summary updated

Abstract

Suppose that some objects are hidden in a finite set S of hiding places that must be examined one by one. The cost of searching subsets of S is given by a submodular function, and the probability t...
BibTeX
@article{fokkink2019submodular,
  author = {Robbert Fokkink and Thomas Lidbetter and László A. Végh},
  title = {{On Submodular Search and Machine Scheduling}},
  journal = {Math. Oper. Res.},
  year = {2019},
  doi = {10.1287/moor.2018.0978},
}
Figure