Nearly Linear Time Optimization via Decreasing Thresholds

This direction is split into other directions: threshold-based greedy selection. Its last version stays readable and citable here.

Version 1 of 166 papers84 conceptsfrozen 2026-10-04

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:

  1. Start High: Set an initial threshold based on the maximum possible single-element gain.
  2. Filter: Pass through the dataset, picking any element that meets the current threshold.
  3. 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:

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.

Papers in this version

Showing 60 of 66 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_nearly_linear_time_optimization_via_decr_71518832,
  title = {Nearly Linear Time Optimization via Decreasing Thresholds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nearly-linear-time-optimization-via-decreasing-thresholds/rdr_7151883224b44d3e9dd8f7f7b8155fda},
  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_nearly_linear_time_optimization_via_decr_71518832_v1,
  title = {Nearly Linear Time Optimization via Decreasing Thresholds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nearly-linear-time-optimization-via-decreasing-thresholds/rdr_7151883224b44d3e9dd8f7f7b8155fda/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}