Parallel Greedy Selection via Threshold Batching

33 concepts24 papers1 proposal

The greedy algorithm is one of the workhorses of modern computer science. To solve complex subset selection problems—like choosing the best features for a machine learning model, placing sensors in an environment, or selecting representative data points for clustering—the greedy strategy is simple: start with an empty set, find the single element that provides the maximum marginal benefit, add it to your set, and repeat.

This sequential approach is highly effective and often comes with strong theoretical guarantees. However, it suffers from a fundamental flaw in the era of big data: it is inherently serial. If you need to select a subset of size $k$, you must run $k$ sequential rounds. In each round, you must evaluate every remaining candidate element relative to the choices made in all previous rounds. This sequential dependency is known as high adaptivity complexity. When datasets scale to billions of elements, this linear bottleneck makes traditional greedy algorithms prohibitively slow.

How can we parallelize a process where every choice seemingly depends on the last? A growing body of research solves this by shifting the paradigm from best-first selection to threshold-based batching.

The Core Intuition: From Best-First to Threshold-First

To break the sequential chain, we must relax our demands. Instead of scanning the entire dataset to find the absolute best element in each round, we ask a simpler question: Which elements are "good enough"?

If we can define a mathematical threshold for what constitutes a high-value element, we can evaluate all remaining candidates in parallel. Every element that exceeds this threshold can be accepted into our solution set simultaneously as a batch.

Traditional Greedy (Sequential):
[Evaluate All] -> Pick Best -> [Evaluate All] -> Pick Best -> ... (k rounds)

Parallel Threshold Greedy (Batch):
[Evaluate All in Parallel] -> Pick ALL above Threshold -> Lower Threshold -> Repeat

This strategy replaces a long chain of sequential dependencies with a few parallel rounds. The algorithm proceeds in descending threshold phases:

  1. Estimate a maximum threshold based on the highest individual element value.
  2. Filter in parallel all elements whose marginal contribution exceeds the current threshold.
  3. Add the qualifying batch to the selected subset.
  4. Decay the threshold by a factor of $(1-\epsilon)$ and repeat until the budget is met or the threshold drops too low.

By accepting batches of elements at once, the number of sequential interactions with the objective function drops from linear in the subset size ($O(k)$) to logarithmic in the total dataset size ($O(\log n)$).

Why It Works: Submodularity and Non-Interference

The primary risk of batch selection is redundancy. If element $A$ and element $B$ both provide high marginal gain individually, a parallel algorithm might select both. However, if they happen to provide the exact same information, adding both to the batch is wasteful. Why does threshold batching avoid this trap?

The answer lies in submodularity—the mathematical formalization of the law of diminishing returns. For a submodular function, the marginal benefit of an element never increases as the selected subset grows.

When we select a batch of elements that all exceed a high threshold $\tau$, submodularity helps us control the loss of quality. Because we only select elements that are exceptionally strong relative to the existing set, they are less likely to completely invalidate each other's contributions, provided we don't over-allocate.

To make this intuition rigorous, researchers have developed several batching mechanisms:

  • Adaptive Sequencing and Prefixes: As explored by Quinzan et al. in Fast Feature Selection with Fairness Constraints, instead of taking all elements above a threshold, algorithms can identify a safe prefix of elements from a sequence that collectively maintain a high average marginal gain. Amanatidis et al. applied a similar parallel prefix selection technique in PARKNAPSACK to handle complex knapsack constraints.
  • Nearly Independent Sets: To prevent redundant coverage during parallel execution, the algorithm designed by Ran et al. in Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem explicitly identifies batches of items that function as a nearly independent set. This ensures that the collective contribution of the batch closely mimics a sequence of high-quality greedy steps without significant internal overlap.
  • Threshold Sampling: Instead of deterministic filtering, Chekuri et al. introduced a greedy sampling technique in Parallelizing greedy for submodular set function maximization in matroids and beyond. By sampling elements that meet a minimum marginal gain threshold, they maintain near-optimal approximation ratios (such as $1 - 1/e$) under complex matroid constraints within a polylogarithmic number of parallel rounds.

Achieving Logarithmic Adaptivity

The crowning theoretical achievement of this research direction is reducing the sequential round complexity to a poly-logarithmic factor of the input size while preserving near-optimal approximation guarantees.

In Submodular Function Maximization in Parallel via the Multilinear Relaxation, the authors demonstrate that elements can be grouped into buckets based on their marginal contributions or gradient values. Updating entire buckets simultaneously allows non-monotone submodular functions to be maximized with minimal sequential rounds.

Similarly, Kuhnle showed in Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization that running multiple greedy passes in parallel using descending thresholds achieves high-quality approximations with nearly linear time complexity. This concept was pushed further by Chen et al. in Breaking Barriers, who introduced a "blended marginal gains" analysis to achieve a state-of-the-art $1/e - \epsilon$ approximation ratio with sublinear adaptivity.

Even when functions deviate from pure submodularity, the thresholding intuition holds. In Batch greedy maximization of non-submodular functions, the authors proved that batching multiple items simultaneously maintains rigorous performance guarantees as long as the objective function's deviation from submodularity remains bounded.

Applications Across Domains

The strategy of replacing sequential greedy choices with parallel threshold-based batches has triggered performance breakthroughs across diverse domains:

Feature Selection and Statistical Learning

In massive datasets, selecting the most predictive features is a major bottleneck. The DASH algorithm, introduced by Qian et al. in Fast Parallel Algorithms for Statistical Subset Selection Problems, leverages threshold-based filtering to reduce parallel rounds from linear to logarithmic relative to the dataset size, achieving near-greedy accuracy with exponential speedups.

Distributed Clustering

Parallel thresholding has fundamentally altered large-scale clustering. In Simple and sharp analysis of k-means||, Rozhon analyzed the industry-standard distributed version of $k$-means++, proving that its "overseeding" strategy—selecting multiple candidate centers simultaneously in each round—achieves a constant-factor approximation in a sub-logarithmic number of communication rounds. For hierarchical $k$-median clustering, Cohen-Addad et al. demonstrated in Parallel and Efficient Hierarchical k-Median Clustering that embedding data into tree metrics allows the marginal benefits of cluster centers to be calculated independently, decoupling the sequential dependencies entirely.

Active Learning

In active learning, standard bisection search requires waiting for a label before choosing the next data point. The authors of DIRECT bypassed this by selecting large batches of examples located near an estimated separation threshold simultaneously. This allows active learning to scale to high-throughput, parallel annotation workflows without losing sample efficiency.

Facility Location

Even practical infrastructure problems benefit from this paradigm. In Placement of Loading Stations for Electric Vehicles: No Detours Necessary!, Nusser et al. modified the greedy algorithm for the hitting set problem to select multiple non-interfering charging station locations in a single iteration, accelerating the solver by eliminating redundant coverage checks.

Conclusion

Parallel greedy selection via threshold batching bridges the gap between the high quality of sequential optimization and the raw speed of parallel computing architectures. By shifting from a strict "pick the single best" mindset to a "pick everything that is good enough" strategy, these algorithms unlock exponential speedups, transforming linear-time bottlenecks into highly parallelizable, logarithmic-round operations.

Key Foundational Work

Parallel Delaunay Refinement: Algorithms and Analyses (2007) — contributed 2 concept elements to this direction.
Parallel chen-han (PCH) algorithm for discrete geodesics (2014) — contributed 1 concept elements to this direction.
Placement of Loading Stations for Electric Vehicles: No Detours Necessary! (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_parallelized_subset_selection_45813dcf,
  title = {parallelized subset selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallelized-subset-selection/rdr_45813dcf2963497fa67f75421496efe4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_parallelized_subset_selection_45813dcf_v1,
  title = {parallelized subset selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallelized-subset-selection/rdr_45813dcf2963497fa67f75421496efe4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake