Submodular Search is Scheduling

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

Introduction

The problem of searching for hidden objects is a fundamental challenge in operations research, with applications ranging from search-and-rescue missions to data retrieval in complex systems. Traditionally, search theory and machine scheduling have been treated as distinct fields. This paper bridges that gap by demonstrating that searching for hidden objects under complex cost and probability constraints is fundamentally a scheduling problem. By framing search through the lens of submodular functions, the authors provide a robust 2-approximation algorithm for this NP-hard problem and solve the game-theoretic version involving an adversarial "Hider."

Problem Formulation: Costs and Probabilities

In a standard search scenario, a searcher explores various locations to find a set of hidden objects. This paper introduces two critical complexities that move beyond simple additive models:

  1. Submodular Costs: The cost of searching is not simply additive. Instead, the marginal cost of searching a new area decreases as more areas are searched (e.g., due to economies of scale or spatial proximity).
  2. Supermodular Probabilities: The probability of finding objects may exhibit "synergy" or clustering, where the likelihood of finding all objects in a specific set is higher than the sum of individual probabilities.

The objective is to find an optimal ordering of locations that minimizes the expected cost to find all hidden objects. Given the combinatorial nature of these constraints, the general problem is NP-hard.

Methodology and Algorithmic Framework

The authors' approach centers on the concept of Search Density ($\rho(A)$), defined as the ratio of the probability of finding the objects in a set $A$ to the cost of searching that set: $$\rho(A) = \frac{g(A)}{f(A)}$$ where $g(A)$ is the supermodular probability function and $f(A)$ is the submodular cost function.

Generalized Sidney Decomposition

A major contribution of this work is the extension of the classic Sidney decomposition—a staple in scheduling theory—to submodular functions. The authors prove that an optimal search sequence must begin with a subset that maximizes this search density. This allows for a recursive decomposition of the problem into manageable components.

Greedy 2-Approximation

Building on the density concept, the authors propose a greedy algorithm that repeatedly selects the "densest" available subset. They demonstrate that this strategy yields a 2-approximation of the optimal expected cost. This result is significant because it matches the best-known bounds for similar scheduling problems while providing a more direct, combinatorial approach.

Polyhedral Combinatorics and Game Theory

The paper also explores a "Game Setting" where a Searcher faces an adversarial Hider. The Hider aims to choose a probability distribution that maximizes the Searcher's expected cost. To solve this, the authors utilize the "base polyhedron" of the submodular cost function. They characterize the Hider's optimal mixed strategies as points within a scaled version of this polyhedron, providing a geometric interpretation of the equilibrium strategies.

Key Theoretical Insights

The Universality of Smith’s Rule

The research reveals that "Smith’s Rule"—a seminal 1956 result for scheduling jobs on a single machine to minimize weighted completion time—is actually a special case of a broader principle governing submodular search. This unification suggests that many search problems can be solved using the intuition developed in the scheduling literature.

The Role of Curvature

The efficiency of the approximation is shown to be sensitive to the "total curvature" ($\kappa$) of the cost function. Curvature measures how much a function deviates from being additive. For cost functions with low curvature (nearly additive), the approximation ratio improves significantly, moving closer to 1.

Series-Parallel Decomposition

The authors identify a specific class of problems—those that are "series-parallel decomposable"—which can be solved optimally in polynomial time. By breaking the search space into smaller, independent sub-problems, the complexity of both the optimization and the game-theoretic variants is reduced, allowing for exact solutions in strongly polynomial time.

Results and Implications

The paper provides a comprehensive theoretical framework for submodular search:

  • Approximation Bounds: A guaranteed 2-approximation, with refined bounds of $\frac{2}{1+\delta}$ based on the curvature of the functions.
  • Game Value: For series-parallel decomposable games, the value of the game is explicitly calculated as $V = \frac{1}{2}(f(S) + \Phi)$, where $\Phi$ represents a term related to the Hider's strategy.
  • New Scheduling Applications: The authors introduce a new scheduling model ($1|prec|\sum w_A h(C_A)$) that accounts for "learning effects," where machine efficiency improves over time, modeled as a concave function of completion times.

Limitations and Future Directions

While the paper provides exact solutions for series-parallel structures, the general computational complexity of finding equilibrium strategies in the submodular search game remains an open question. Future research may focus on developing a metric to quantify how "far" a problem is from being series-parallel, which could lead to tighter approximation bounds for near-decomposable cases. Additionally, extending the model to include multiple "selfish" hiders could provide insights into decentralized systems and multi-agent scheduling environments.

Summary updated

BibTeX
@article{fokkink2019submodular,
  author = {Robbert Fokkink and Thomas F. Lidbetter and László A. Végh},
  title = {{Submodular Search is Scheduling}},
  journal = {Math. Oper. Res.},
  year = {2019},
  doi = {10.1287/moor.2018.0978},
}
Figure