Parallelizing Greedy Optimization via Low Adaptivity

This direction is split into other directions: sequential selection bottleneck. Its last version stays readable and citable here.

Version 1 of 1108 papers119 conceptsfrozen 2026-10-04

The greedy algorithm is the workhorse of combinatorial optimization. Whether you are selecting a diverse set of news articles, finding a maximum matching in a graph, or choosing features for a machine learning model, the recipe is the same: start with an empty set and repeatedly add the element that provides the highest marginal gain.

This strategy is popular because it works. For many NP-hard problems, particularly those involving submodular functions (functions with diminishing returns), the greedy approach provides a provably near-optimal solution. However, the greedy algorithm has a fundamental flaw in the era of Big Data: it is "inherently sequential." Each choice depends on the results of every previous choice. If you need to select 10,000 items from a dataset of a billion, you must perform 10,000 sequential rounds of computation.

Recent research has focused on breaking this serial bottleneck. The goal is to design algorithms with low adaptivity—reducing the number of sequential rounds from $O(n)$ to $O(\log n)$ or even $O(1)$, allowing us to leverage the massive parallelism of modern clusters and GPUs.

The Adaptivity Bottleneck

In distributed computing, the primary cost is often not the computation itself, but the "rounds" of communication between machines. Eric Balkanski and Yaron Singer formalized this as adaptive complexity: the minimum number of sequential rounds of queries needed to achieve a certain approximation guarantee.

Standard greedy algorithms are highly adaptive. As Alina Ene and Huy L. Nguyen point out in Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time, this serial dependency prevents us from using modern parallel architectures. If each step requires a global sync to find the "best" next item, the system spends more time waiting for network updates than doing math.

Strategy 1: Composable Coresets

One way to parallelize greedy is to move from a "one-at-a-time" approach to a "divide-and-conquer" approach. This is the intuition behind composable coresets.

In Distributed Submodular Maximization: Identifying Representative Elements in Massive Data, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause introduced GreeDi. The idea is simple:

  1. Partition the massive dataset across $m$ machines.
  2. Each machine runs a local greedy algorithm to pick a small "representative" subset.
  3. These subsets are merged on a single machine, which runs one final greedy pass.

The magic lies in the submodularity: if an item is "valuable" in a local partition, it is likely to be valuable globally. Sepehr Assadi and Vahab Mirrokni extended this logic to graph problems in Distributed Weighted Matching via Randomized Composable Coresets, showing that even for complex matching problems, a two-round MapReduce approach can maintain nearly 99% of the solution quality of a centralized greedy algorithm.

Strategy 2: Adaptive Sequencing and Thresholding

While coresets work well for simple constraints, they can struggle with more complex ones. A more robust approach is Adaptive Sequencing. Instead of picking the single best item, we pick a batch of items that are "good enough."

Balkanski, Singer, and Aviad Rubinstein demonstrated in An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model that we can achieve the optimal $1-1/e$ approximation in only polylogarithmic rounds.

The intuition is to set a threshold for marginal gain. In each round, the algorithm identifies all items that provide a gain above this threshold and adds a large, random subset of them to the solution. If too few items meet the threshold, the threshold is lowered. This "batching" allows the algorithm to jump forward, selecting many items in parallel rather than one by one. Kai Han and Jing Tang applied similar "random batch selection" techniques to non-monotone functions in Practical Parallel Algorithms for Non-Monotone Submodular Maximization, drastically reducing the number of sequential rounds needed in practice.

Strategy 3: Randomized Sketching and Sparsification

In some domains, like linear algebra or graph theory, the "greedy" part isn't just about picking items; it's about making structural decisions. For example, in QR Decomposition with Column Pivoting, the algorithm greedily picks the column that is "most different" from the ones already chosen.

Traditionally, this is a serial nightmare because every choice requires updating the entire matrix. Jed A. Duersch solved this in Randomized QR with Column Pivoting by using randomized sketching. By projecting the matrix into a lower-dimensional space, we can pick a whole block of pivots at once. This allows the use of high-performance "blocked" linear algebra routines (Level 3 BLAS) that are orders of magnitude faster on modern hardware.

Similarly, in graph coloring, Sepehr Assadi and colleagues introduced the Palette-Sparsification Theorem in Sublinear Algorithms for (Δ+ 1) Vertex Coloring. They proved that if every vertex just picks a tiny random subset of colors to choose from, a valid coloring still exists. This reduces the global dependency of the greedy coloring process, enabling massively parallel computation.

Why It Works: The Power of Diminishing Returns

The reason these parallel strategies work is the very property that makes greedy attractive in the first place: submodularity.

Because the marginal value of an item generally decreases as the set grows, the "mistakes" we make by picking items in parallel (without knowing exactly what our peers picked) are limited. If an item is great now, it's likely still pretty good even if someone else adds a different item to the set at the same time. By trading a tiny bit of approximation quality for a massive reduction in adaptivity, these researchers have turned the sequential "serial killer" into a parallel powerhouse.

Papers in this version

Showing 60 of 108 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_parallelizing_greedy_optimization_via_lo_d63cb2b7,
  title = {Parallelizing Greedy Optimization via Low Adaptivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallelizing-greedy-optimization-via-low-adaptivity/rdr_d63cb2b7a1d447938ea3482d84fef109},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_parallelizing_greedy_optimization_via_lo_d63cb2b7_v1,
  title = {Parallelizing Greedy Optimization via Low Adaptivity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallelizing-greedy-optimization-via-low-adaptivity/rdr_d63cb2b7a1d447938ea3482d84fef109/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}