Distributed Submodular Maximization

54 concepts37 papers1 proposal

Submodular functions formalize the intuitive concept of diminishing returns: adding an item to a small selection provides greater marginal utility than adding that same item to a larger selection. This mathematical property underpins many real-world optimization problems, such as selecting a representative summary of a massive dataset, deploying sensors to maximize information gain, or coordinating multi-robot fleets.

In a centralized setting, a simple sequential greedy algorithm—which iteratively selects the item with the highest marginal gain—is guaranteed to achieve at least a $(1 - 1/e) \approx 63\%$ approximation of the optimal solution. However, as datasets grow to billions of entries or systems become decentralized across peer-to-peer networks, a single central coordinator becomes a severe bottleneck for memory, computation, and communication.

Distributed submodular maximization solves this challenge by breaking the optimization problem apart, allowing multiple machines or autonomous agents to compute high-quality solutions in parallel while maintaining strict theoretical performance guarantees.

The Two-Stage Framework and the Proxy Property

The most straightforward way to distribute a submodular maximization problem is to partition the data across a cluster of machines. However, because submodular utility depends on the global context of what has already been selected, independent local decisions risk introducing massive redundancies.

The breakthrough that makes parallel selection viable is the statistical proxy property of submodular functions under random partitioning. As demonstrated by Karbasi et al. in their GreeDi framework (Distributed Submodular Maximization), evaluating a submodular objective on a random local partition serves as a statistically sound proxy for the global objective. Because of diminishing returns, if an element provides exceptional marginal utility within a local random subset, it is highly likely to be a globally valuable representative.

This insight enables a highly efficient two-stage distributed framework:

[Massive Dataset] ───> Random Partitioning ───> [Node 1] ───> Local Greedy Selection ───┐
                                           ───> [Node 2] ───> Local Greedy Selection ───┼───> [Central Merge] ───> Final Global Greedy Pass
                                           ───> [Node 3] ───> Local Greedy Selection ───┘
  1. Local Selection: The ground dataset is partitioned across multiple nodes. Each node independently executes a standard sequential greedy algorithm on its local subset to produce a compact summary.
  2. Global Merge: A central coordinator collects these local summaries, merges them into a single candidate pool, and runs a final global greedy pass to select the ultimate representative set.

Mirzasoleiman et al. showed in Distributed Submodular Maximization: Identifying Representative Elements in Massive Data that this two-stage protocol retains between 90% and 98% of the solution quality found in non-distributed settings while scaling to tens of millions of data points. To scale even further without overloading the central coordinator's memory, frameworks like the one proposed by Lucic et al. employ multi-round, tree-based compression strategies that remain horizontally scalable on fixed-capacity machines.

This two-stage mechanism can be formalized using the concept of composable core-sets—small subsets of data that can be computed independently and combined such that the optimization over their union closely approximates the optimization over the entire dataset. Mirrokni et al. leveraged randomized composable core-sets in Randomized Composable Core-sets for Distributed Submodular Maximization to deliver the first constant-round, constant-factor approximation algorithms suitable for MapReduce and streaming environments.

Decentralization via Continuous Lifting and Gradient Tracking

While the two-stage framework excels in data centers, it still relies on a central coordinator to execute the final merge step. In edge networks, multi-robot fleets, or decentralized sensor networks, relying on a central coordinator introduces a single point of failure and prohibitive long-range communication costs.

To eliminate the coordinator entirely, researchers shift the problem from discrete selection to continuous optimization. This is achieved through continuous lifting: mapping discrete choices into a continuous space using the multilinear extension of the submodular function. In this continuous domain, the problem becomes one of maximizing a continuous diminishing-returns (DR-submodular) function.

Mokhtari et al. introduced the Decentralized Continuous Greedy (DCG) algorithm in Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings. Instead of routing data to a central hub, nodes maintain a local fractional solution and update it by communicating solely with their immediate network neighbors.

The core challenge in this peer-to-peer setting is that no individual node knows the global objective function. To navigate the continuous space accurately, nodes utilize a mechanism called gradient tracking. As developed by Chao Zhang et al. in Decentralized Gradient Tracking for Continuous DR-Submodular Maximization, each node tracks and estimates the global gradient of the multilinear extension by exchanging local gradient estimates with its neighbors.

$$\mathbf{x}_{i}^{(t+1)} = \mathbf{x}_{i}^{(t)} + \gamma \cdot \text{Frank-Wolfe-Step}(\mathbf{d}_i^{(t)})$$

Where $\mathbf{d}_i^{(t)}$ is the tracked global gradient estimate at node $i$. By combining gradient tracking with Frank-Wolfe style updates, the nodes reach a consensus on the optimal continuous fractional solution, achieving the theoretical $(1 - 1/e)$ performance limit of centralized algorithms without ever sharing raw data. To ensure practical efficiency, Xu et al. integrated variance reduction techniques in Sample Efficient Decentralized Stochastic Frank-Wolfe Methods for Continuous DR-Submodular Maximization, allowing the network to simultaneously minimize local gradient noise and network-wide consensus errors using significantly fewer data samples.

Robustness and Resource Awareness at the Edge

In real-world distributed deployments, algorithms must contend with physical constraints: limited communication bandwidth, changing network topologies, and unexpected node failures or data deletions.

In multi-robot coordination tasks, such as area coverage or target tracking, communication overhead can easily overwhelm the network if robots must constantly synchronize states. To address this, Zirui Xu et al. developed the Resource-Aware distributed Greedy (RAG) algorithm in Communication- and Computation-Efficient Distributed Decision-Making in Multi-Robot Networks. Instead of global broadcasts, robots calculate marginal gains locally and restrict communication to immediate neighbors, achieving linear scaling ($O(N)$) and running up to 1,000 times faster than traditional methods. When the communication network itself needs to adapt, the Anaconda framework proposed by Tzoumas et al. allows agents to dynamically self-configure their communication topology, balancing the trade-off between decision speed and coordination quality (Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Design).

Another critical requirement for modern distributed systems is resilience against data loss or adversarial attacks. If a subset of items or nodes is removed from the system—whether due to hardware failure or privacy compliance like the "right to be forgotten"—the remaining selection must still retain high utility.

Bogunovic et al. tackled this in A distributed algorithm for partitioned robust submodular maximization by designing the D-PRO algorithm. By understanding how submodular functions behave under random partitioning, the authors proved that a two-stage selection process can be made inherently deletion-robust. Because the initial partitioning distributes influential elements evenly across local candidate sets, the central coordinator can reconstruct a high-quality global solution even if an adversary removes a significant portion of the dataset before the final selection is finalized. This architecture ensures that parallel processing and structural robustness can be achieved simultaneously at scale (Deletion-Robust Submodular Maximization at Scale).

Key Foundational Work

Online Distributed Sensor Selection (2010) — contributed 1 concept elements to this direction.
Towards preserving privacy in participatory sensing (2011) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 35 papers
  2. Version 1 · 2026-10-04 · 38 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_distributed_submodular_maximization_c51c8a02,
  title = {distributed submodular maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distributed-submodular-maximization/rdr_c51c8a02cf754fbe9532b56f8f812478},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_distributed_submodular_maximization_c51c8a02_v2,
  title = {distributed submodular maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/distributed-submodular-maximization/rdr_c51c8a02cf754fbe9532b56f8f812478/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake