Submodular functions are the mathematical workhorses of data summarization, viral marketing, and sensor placement. They capture the intuitive principle of diminishing returns: the marginal value of adding an element to a set decreases as the set grows larger.
For decades, the "Greedy Algorithm"—which picks the single best element, adds it to the set, and repeats—has been the gold standard. It is simple and achieves a celebrated $(1 - 1/e)$ approximation ratio. However, the greedy algorithm is inherently sequential. To pick $k$ elements, you must perform $k$ sequential rounds of computation. When $k$ is large and the dataset contains billions of items, this sequential bottleneck makes the algorithm unusable on modern parallel hardware.
A recent surge in research has reimagined these algorithms to minimize adaptive complexity (or "adaptivity"): the number of sequential rounds of interaction with the objective function. By reducing adaptivity from linear to logarithmic or even constant rounds, researchers have unlocked the ability to process massive datasets across thousands of processors simultaneously.
The Adaptivity Bottleneck
In distributed computing, the primary cost is often not the total number of calculations, but the number of communication rounds between machines. Eric Balkanski and Yaron Singer formalized this in Approximation Guarantees for Adaptive Sampling, showing a fundamental trade-off between the number of sequential rounds and the achievable approximation ratio.
The goal of this research direction is to reach the "Holy Grail": algorithms that achieve the optimal approximation ratio (like $1 - 1/e$ for monotone functions) in only $O(\log n)$ rounds. Alina Ene and Huy L. Nguyen achieved this theoretical breakthrough in Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time, proving that high-quality solutions do not strictly require sequential processing.
From Greedy Selection to Batch Thresholding
The core intuition behind low-adaptivity algorithms is a shift from selection to filtering. Instead of searching for the single best element in each round, these algorithms identify a batch of elements that all provide a "good enough" marginal gain.
- Thresholding: The algorithm sets a high value threshold.
- Parallel Sampling: It identifies all elements in the dataset that exceed this threshold relative to the current set.
- Batch Addition: It adds a large subset of these elements to the solution simultaneously.
- Decay: The threshold is lowered, and the process repeats.
This mechanism is central to the FAST algorithm, introduced by Adam Breuer, Eric Balkanski, and Yaron Singer in The FAST Algorithm for Submodular Maximization. By replacing "adaptive sampling" with "adaptive sequencing," FAST achieves the optimal approximation ratio while running orders of magnitude faster than sequential greedy approaches on real-world hardware.
Scaling to Complex Constraints
Real-world problems rarely involve simple size limits. We often face knapsack constraints (where items have different costs) or matroid constraints (which model complex structural dependencies).
Parallelizing these is significantly harder because a batch of elements that looks good individually might violate the constraint when added together. Georgios Amanatidis and Stefano Leonardi addressed this in Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity, introducing PARKNAPSACK. This algorithm achieves a constant-factor approximation in $O(\log n)$ rounds, proving that non-uniform costs do not prevent massive parallelization.
For even more general constraints, Kai Han and Jing Tang developed ParSKP and ParSSP in Practical Parallel Algorithms for Non-Monotone Submodular Maximization. These algorithms bypass expensive mathematical simulations (like multilinear extensions) in favor of combinatorial "random batch selection," making them highly practical for distributed clusters.
Non-Monotone Functions and Diversity
In many tasks, like image summarization, adding an element might actually decrease the total value if it introduces redundancy. These are non-monotone functions.
The challenge here is that you cannot simply keep adding elements; you must decide when to stop or even what to exclude. Eric Balkanski and colleagues tackled this with BLITS in Non-monotone Submodular Maximization in Exponentially Fewer Iterations, achieving an exponential speedup over previous methods. More recently, Canh V. Pham and Tan D. Tran introduced the AST (Alternate Threshold) algorithm in Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint, which pushes the approximation ratio for parallel non-monotone maximization to $7 + \epsilon$ while maintaining $O(\log n)$ adaptivity.
The Impact of Low Adaptivity
The shift toward low-adaptivity algorithms has transformed submodular optimization from a sequential bottleneck into a parallel-friendly primitive. Whether it is Baharan Mirzasoleiman and Andreas Krause using DISCOVER to summarize social graphs with billions of edges in Distributed Submodular Cover: Succinctly Summarizing Massive Data, or Alan Kuhnle leveraging sublinear adaptivity to speed up MapReduce frameworks in DASH, the result is the same: we can now find near-optimal subsets in massive data in a fraction of the time previously required.