The classic greedy algorithm is the foundational workhorse for combinatorial optimization. To maximize a submodular function—where items exhibit a "diminishing returns" property—the standard greedy approach scans the entire remaining pool of items, identifies the single element that yields the absolute highest marginal gain, and adds it to the solution set.
While conceptually simple and theoretically powerful, this exhaustive search introduces a severe computational bottleneck. If you have a ground set of $n$ elements and need to select a budget of $k$ items, the algorithm must perform $O(nk)$ function evaluations. When dealing with massive modern datasets where $n$ is in the millions, this quadratic-style query complexity becomes prohibitively expensive.
To break this bottleneck, a powerful paradigm shift has emerged: decreasing threshold greedy selection. Instead of searching for the absolute best element at every step, these algorithms filter elements using an adaptive, decaying quality threshold. This simple relaxation collapses the query complexity from quadratic to nearly linear—or even "clean" linear time—without sacrificing provable approximation guarantees.
The Core Mechanism: From Searching to Filtering
The fundamental shift of threshold-based greedy optimization is moving from an exhaustive search to a satisficing filter.
Instead of scanning the entire ground set to find $\arg\max_{e} \Delta(e|S)$, where $\Delta(e|S)$ represents the marginal contribution of element $e$ to the current solution $S$, the algorithm maintains a value threshold $\tau$. It iterates through the ground set and immediately selects any element that satisfies:
$$\Delta(e|S) \ge \tau$$
As soon as an element meets this benchmark, it is added to the solution. The algorithm does not waste time checking if a later element might be marginally better.
Standard Greedy: [Scan all n elements] -> Pick absolute best -> Repeat k times (O(nk))
Threshold Greedy: [Scan elements] -> Pick ANY element >= τ -> If none, lower τ -> Repeat
What happens when a full pass over the data yields no elements that satisfy the current threshold? The algorithm systematically lowers the threshold by a fixed decay factor (typically $\tau \leftarrow \tau(1-\epsilon)$) and restarts the filtering process. As noted by Sebastian Pokutta, this decremental thresholding strategy replaces global optimization with a sequence of restarts that gradually relax the quality requirement. Xianyue Li et al. highlight that these threshold descent criteria drastically reduce time complexity while preserving robust approximation bounds.
Why It Works: The Geometry of Diminishing Returns
It is highly intuitive that filtering is faster than searching, but why does it remain accurate? Why does picking elements out of order based on a threshold not lead to terrible, sub-optimal solutions?
The answer lies in the core mathematical property of submodularity itself: diminishing returns. For a submodular function, the marginal gain of any element can only decrease or stay the same as the solution set grows.
Because of this property, if we encounter an element $e$ that satisfies $\Delta(e|S) \ge \tau$, we know that its value will never be higher than it is right now. Waiting to see if other elements are better provides no benefit to element $e$ itself; its potential contribution will only decay as other items are added. By accepting it immediately, we "lock in" a guaranteed level of utility relative to our current threshold.
Crucially, because the threshold $\tau$ decreases exponentially by a factor of $1-\epsilon$, the total number of threshold updates is strictly bounded by the range of possible marginal values, independent of the size of the dataset $n$. The algorithm only needs to make a small, predictable number of passes over the ground set. As a result, Wenxin Li et al. demonstrated that this mechanism can achieve a tight $(1 - 1/e - \epsilon)$ approximation ratio for cardinality constraints in "clean" linear time, completely removing messy logarithmic factors from the complexity scaling.
Managing Costs and Complex Constraints
Real-world optimization problems rarely feature uniform item costs or simple cardinality constraints. Fortunately, the decreasing threshold framework adapts seamlessly to more intricate environments by shifting the threshold from absolute marginal gain to marginal density.
When elements have non-uniform costs, the selection criterion is modified to evaluate the gain-to-cost ratio:
$$\frac{\Delta(e|S)}{c(e)} \ge \tau$$
In this setup, the algorithm maintains an adaptive density threshold. Canh V. Pham et al. leveraged this strategy to design the first constant-factor approximation algorithms for non-monotone submodular maximization under knapsack constraints operating within linear query complexity. By iteratively lowering this density threshold, the algorithm balances the budget consumption against the utility gained. To further refine this process, Canh V. Pham introduced an adaptive density thresholding algorithm (EDL) that narrows the gap between theoretical bounds and practical performance, scaling efficiently to massive datasets.
This thresholding logic extends naturally to other complex constraint structures. For instance, Kai Han et al. incorporated decreasing marginal gain thresholds to optimize submodular functions subject to matroid constraints, proving that perfectly greedy selection is not required at every step to maintain high solution quality.
Generalizations Beyond Simple Sets
The utility of decreasing thresholds is not confined to binary set selection; it has been generalized across several advanced combinatorial domains:
- Non-Monotone Functions: When adding elements can actually decrease the total value of the objective function, standard greedy approaches fail. To solve this, Alan Kuhnle developed an interlaced greedy algorithm. By running two threshold-based selection procedures concurrently and alternating their choices, the algorithm breaks the quadratic time barrier for non-monotone functions. Yixin Chen et al. expanded on this by guiding the descending threshold framework with a fast local search, pushing approximation ratios beyond the traditional $1/e$ barrier in nearly linear time.
- The Integer Lattice: In many applications, decisions are multi-unit (e.g., deciding how much of a resource to allocate rather than just whether to allocate it). Tasuku Soma et al. generalized submodular cover to the integer lattice using a decreasing efficiency threshold, providing massive speedups when the range of integer values is large. Similarly, Alan Kuhnle et al. developed the ThresholdGreedy and FastGreedy algorithms to maximize non-submodular, monotonic functions on the integer lattice.
- Multi-Type Selection ($k$-Submodularity): When items have both a location and a specific type or state, the search space expands drastically. Guanyu Nie et al. successfully applied decreasing thresholds to size-constrained $k$-submodular maximization, removing the computational bottleneck that traditionally scales with the total budget.
Broad Algorithmic Applications
The core intuition—replacing an exhaustive search for the maximum with an exponentially decaying acceptance threshold—reverberates across many related fields:
- Signal Processing: In sparse signal recovery, Jian Wang et al. developed Generalized Orthogonal Matching Pursuit (gOMP), which selects multiple indices per iteration rather than a single best index, balancing computational speed and reconstruction accuracy.
- Data and Sensor Selection: Selecting optimal data sources for Bayesian learning is inherently expensive. Lintao Ye et al. showed that threshold-based greedy selection reduces this complexity from quadratic to near-linear, offering a controllable trade-off between a marginal increase in error and a massive reduction in runtime.
- Surrogate Optimization: Kai Wei et al. introduced MULTGREED, a multi-stage framework that filters data through cheap proxy functions using an approximation threshold before evaluating the full target function, yielding up to a 1,000x speedup on large speech datasets.
- Market and Graph Mechanisms: In online platform markets, Zhenzhe Zheng et al. proved that the search space for revenue-maximizing product displays can be reduced to a linear set of quality-ordered thresholds. In stochastic network optimization, Evripidis Bampis et al. utilized a two-stage strategy that filters elements based on whether their probability of being mandatory exceeds a specific threshold, balancing immediate query costs against long-term optimization risks.
By shifting the algorithmic goal from finding the absolute best element to finding any sufficiently good element, decreasing threshold algorithms exploit the natural geometry of diminishing returns. This elegant modification bypasses the quadratic complexity of traditional greedy search, providing a scalable blueprint for big-data combinatorial optimization.
Key Foundational Work
A rank-predicted pseudo-greedy approach to efficient text selection from large-scale corpus for maximum coverage of target units (2008) — contributed 1 concept elements to this direction.
Generalized Orthogonal Matching Pursuit (2011) — contributed 1 concept elements to this direction.