Scaling Submodular Maximization to Linear Time

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2281 papers322 conceptsfrozen 2026-10-04

Submodular functions are the mathematical embodiment of the "law of diminishing returns." In fields ranging from data summarization and sensor placement to viral marketing, we often want to select a subset of items that maximizes a utility function where each additional item adds less value than the one before it.

While the classic Greedy Algorithm provides a strong theoretical guarantee—achieving at least $1 - 1/e \approx 63\%$ of the optimal value—it faces a severe scalability crisis. As datasets grow to millions of points, the standard approach of repeatedly scanning the entire dataset becomes a computational bottleneck. Recent research has focused on breaking this "quadratic-like" complexity to achieve nearly-linear time algorithms.

The Quadratic Bottleneck

To understand the problem, consider the standard greedy process for selecting $k$ items from a set of $n$ elements. In each of the $k$ rounds, the algorithm must evaluate the "marginal gain" of every remaining element to find the best one to add. This requires $O(nk)$ function evaluations.

As noted by Moran Feldman, Wenxin Li, and colleagues in Submodular Maximization in Clean Linear Time, this $O(nk)$ complexity is effectively quadratic when the budget $k$ scales with the dataset size $n$. For modern applications like summarizing a billion-image dataset, $10^{15}$ operations is simply not feasible.

The Power of Random Subsampling

The first major breakthrough in scaling these methods was the realization that we don't need to find the absolute best element in every round. A "good enough" element will suffice.

In Lazier Than Lazy Greedy, Baharan Mirzasoleiman, Andreas Krause, and their co-authors introduced STOCHASTIC-GREEDY. Instead of searching all $n$ elements, the algorithm samples a small random subset of size $\frac{n}{k} \log \frac{1}{\epsilon}$ and picks the best element from that sample.

The intuition is rooted in the concentration of measure: a small random sample is highly likely to contain an element whose contribution is close to the average of the top-tier elements. This simple tweak reduces the complexity from $O(nk)$ to $O(n \log \frac{1}{\epsilon})$, making the runtime independent of the solution size $k$. Christopher Harshaw and Amin Karbasi further demonstrated in The Power of Subsampling in Submodular Maximization that this strategy delivers state-of-the-art results at a fraction of the cost.

Thresholding and Parallelism

Another way to avoid the $O(nk)$ scan is to use thresholding. Instead of looking for the maximum gain, we look for any element that exceeds a certain value threshold.

This idea is central to the FAST (Fast Adaptive Sequencing Technique) algorithm developed by Adam Breuer, Eric Balkanski, and Yaron Singer in The FAST Algorithm for Submodular Maximization. By adaptively lowering a threshold and selecting all elements that meet it in parallel, they achieved the optimal $1-1/e$ ratio with logarithmic "adaptivity" (sequential rounds).

For non-monotone functions—where adding an item might actually decrease the total value (e.g., adding a redundant image to a summary)—Canh V. Pham and Tan D. Tran introduced the Alternate Threshold (AST) algorithm in Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint. AST manages the delicate balance of non-monotonicity by using dual thresholds to ensure that elements are only added if they provide a significant net gain relative to the remaining capacity.

Streaming and Dynamic Updates

In many real-world scenarios, we don't have the luxury of storing the entire dataset. We need to make decisions "on the fly."

  • Streaming: Algorithms like Streaming Local Search recycle discarded elements to handle non-monotone objectives in a single pass. Alina Ene and Huy L. Nguyen developed primal-dual frameworks for Streaming Monotone k-Submodular Maximization, allowing for high-throughput processing where the computational budget per element is extremely tight.
  • Dynamic: When data is constantly being inserted and deleted (like a social media feed), we need algorithms that update the solution without recomputing from scratch. Paul Duetting and Silvio Lattanzi provided the first fully dynamic algorithms for matroids, maintaining a constant-factor approximation in amortized time that scales with the rank of the constraint rather than the size of the ground set.

Reducing Oracle Costs via Memoization

Even with linear-time algorithms, the "hidden constant" is often the cost of the value oracle—the function $f(S)$ itself. Evaluating the diversity of a massive set of documents or the coverage of a sensor network can be expensive.

Jeff Bilmes proposed a Memoization Framework to address this. Instead of treating the objective as a black box, this approach maintains internal statistics about the current set $S$. By precomputing and updating these statistics, the cost of evaluating a marginal gain can be reduced from a full function evaluation to a simple metadata lookup, drastically speeding up both greedy and local search methods.

The Theoretical Speed Limit

Is it possible to do better than linear time? In Submodular Maximization in Clean Linear Time, researchers established a fundamental "speed limit": any algorithm that guarantees a constant approximation ratio must, at a minimum, examine a linear number of elements.

This marks the culmination of the research direction: moving from the $O(nk)$ complexity of the 1970s to the $O(n)$ "clean" linear time required for the era of Big Data. By combining random sampling, adaptive thresholding, and efficient memoization, these modern algorithms allow us to apply the principle of diminishing returns to datasets of virtually any scale.

Papers in this version

Showing 60 of 281 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 329 papers
  2. Version 1 · 2026-10-04 · 281 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_submodular_optimization_scalability_46b95753,
  title = {submodular optimization scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-optimization-scalability/rdr_46b957530a704b7e9652b2d20d751672},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_submodular_maximization_to_linea_46b95753_v1,
  title = {Scaling Submodular Maximization to Linear Time},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-submodular-maximization-to-linear-time/rdr_46b957530a704b7e9652b2d20d751672/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}