# Optimal Algorithms for Submodular Maximization with Distributed Constraints

arXiv: https://arxiv.org/abs/1909.13676 · HTML: https://mlsanity.com/paper/1909.13676/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2019.

## Built on by (most cited first, 9 of 9)

- [Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making](https://mlsanity.com/paper/2204.07520/) (2022)
- [Bandit Submodular Maximization for Multi-Robot Coordination in Unpredictable and Partially Observable Environments](https://mlsanity.com/paper/2305.12795/) (2023)
- [Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination](https://mlsanity.com/paper/2209.12429/) (2022)
- [Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks](https://mlsanity.com/paper/2407.10382/) (2024)
- [Leveraging Untrustworthy Commands for Multi-Robot Coordination in Unpredictable Environments: A Bandit Submodular Maximization Approach](https://mlsanity.com/paper/2309.16161/) (2023)
- [GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions](https://mlsanity.com/paper/2403.10332/) (2024)
- [Performance-Aware Self-Configurable Multi-Agent Networks: A Distributed Submodular Approach for Simultaneous Coordination and Network Design](https://mlsanity.com/paper/2409.01411/) (2024)
- [Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach](https://mlsanity.com/paper/2603.27803/) (2026)
- [Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations](https://mlsanity.com/paper/2607.00680/) (2026)

## Abstract (arXiv)

We consider a class of discrete optimization problems that aim to maximize a submodular objective function subject to a distributed partition matroid constraint. More precisely, we consider a networked scenario in which multiple agents choose actions from local strategy sets with the goal of maximizing a submodular objective function defined over the set of all possible actions. Given this distributed setting, we develop Constraint-Distributed Continuous Greedy (CDCG), a message passing algorithm that converges to the tight (1-1/e) approximation factor of the optimum global solution using only local computation and communication. It is known that a sequential greedy algorithm can only achieve a 1/2 multiplicative approximation of the optimal solution for this class of problems in the distributed setting. Our framework relies on lifting the discrete problem to a continuous domain and developing a consensus algorithm that achieves the tight (1-1/e) approximation guarantee of the global discrete solution once a proper rounding scheme is applied. We also offer empirical results from a multi-agent area coverage problem to show that the proposed method significantly outperforms the state-of-the-art sequential greedy method.