The "Greedy" algorithm is the workhorse of combinatorial optimization. To maximize a function, you simply pick the element that provides the largest immediate gain, add it to your set, and repeat. This simple strategy is surprisingly effective for submodular functions—mathematical models of "diminishing returns"—where it often achieves the best possible approximation ratio.
However, as datasets scale into the millions, the standard greedy approach hits a wall. If you have $n$ items and need to select $k$ of them, you must perform $O(nk)$ evaluations. In many real-world scenarios, $k$ is proportional to $n$, leading to a quadratic $O(n^2)$ complexity that is computationally prohibitive for "big data."
The Intuition of "Good Enough"
The core insight driving recent breakthroughs is that we don't actually need to find the absolute best element at every step. Because of the diminishing returns property, if an element is "good enough" to provide a high marginal gain now, it is likely to be one of the top choices overall.
Instead of scanning the entire remaining dataset to find the maximum gain, we can set a threshold. We then iterate through the data and accept the first element we encounter that exceeds this threshold. This simple shift transforms a global search into a local check, drastically reducing the number of function evaluations.
The Decreasing Threshold Mechanism
To maintain high solution quality, researchers like Alan Kuhnle and Moran Feldman have developed a "decreasing threshold" framework. The process works in rounds:
- Start High: Set an initial threshold based on the maximum possible single-element gain.
- Filter: Pass through the dataset, picking any element that meets the current threshold.
- Lower and Repeat: Once no more elements meet the threshold, decrease it (usually by a multiplicative factor like $1-\epsilon$) and start a new pass.
In Nearly Linear-Time, Deterministic Algorithm for Maximizing (Non-Monotone) Submodular Functions Under Cardinality Constraint, Alan Kuhnle demonstrates that this "interlacing" of greedy passes allows deterministic algorithms to achieve near-optimal results in time that scales almost linearly with the size of the ground set. Similarly, Moran Feldman and colleagues showed in Submodular Maximization in Clean Linear Time that it is possible to achieve the optimal $1-1/e$ guarantee in "clean" $O(n)$ time by systematically decreasing the quality threshold as items are added.
Scaling to Complex Constraints
This thresholding logic extends beyond simple size constraints. When dealing with knapsack constraints (where items have different costs), Canh V. Pham introduced the EDL algorithm, which uses an adaptive density threshold (gain-to-cost ratio) to maintain linear query complexity.
For even more complex structures like matroids, Eric Balkanski and Yaron Singer proposed "adaptive sequencing" in An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model. By identifying prefixes of elements that maintain high marginal gains, they allow for the simultaneous selection of many elements, enabling massive parallel speedups.
Beyond Submodularity
The power of threshold-based selection is a general principle appearing across diverse fields:
- Signal Processing: In Orthogonal Matching Pursuit with Thresholding and its Application in Compressive Sensing, Frank de Hoog shows that replacing the expensive search for the "best" matching atom with a simple thresholding step maintains exact reconstruction guarantees while slashing complexity.
- Online Decision Making: In the Prophet Secretary problem, Hossein Esfandiari and others use thresholds calculated via backward recurrence to optimize selection from a stream of random arrivals.
- Algorithm Restarts: Sebastian Pokutta argues in Restarting Algorithms: Sometimes There Is Free Lunch that decremental thresholding can be viewed as a "black-box" meta-technique to boost convergence rates by strategically restarting algorithms with updated parameters.
By moving from a "search for the best" to a "filter for the sufficient" mindset, this research direction has made high-quality optimization feasible for the massive datasets of the modern era.