# Jacobi-Style Iteration for Distributed Submodular Maximization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2020.

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

- [Resource-Aware Distributed Submodular Maximization: A Paradigm for Multi-Robot Decision-Making](https://mlsanity.com/paper/2204.07520/) (2022)
- [Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks](https://mlsanity.com/paper/2407.10382/) (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)

This paper presents a novel Jacobi-style iteration algorithm for solving the problem of distributed submodular maximization, in which each agent determines its own strategy from a finite set so that the global submodular objective function is jointly maximized. Building on the multi-linear extension of the global submodular function, we expect to achieve the solution from a probabilistic, rather than deterministic, perspective, and thus transfer the considered problem from a discrete domain into a continuous domain. Since it is observed that an unbiased estimation of the gradient of multi-linear extension function~can be obtained by sampling the agents' local decisions, a projected stochastic gradient algorithm is proposed to solve the problem. Our algorithm enables the distributed updates among all individual agents and is proved to asymptotically converge to a desirable equilibrium solution. Such an equilibrium solution is guaranteed to achieve at least 1/2-suboptimal bound, which is comparable to the state-of-art in the literature. Moreover, we further enhance the proposed algorithm by handling the scenario in which agents' communication delays are present. The enhanced algorithmic framework admits a more realistic distributed implementation of our approach. Finally, a movie recommendation task is conducted on a real-world movie rating data set, to validate the numerical performance of the proposed algorithms.