# Optimality Gap of Decentralized Submodular Maximization under Probabilistic Communication

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Sep 2024.

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

- [Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations](https://mlsanity.com/paper/2607.00680/) (2026)

## Abstract (arXiv)

This paper considers the problem of decentralized submodular maximization subject to partition matroid constraint using a sequential greedy algorithm with probabilistic inter-agent message-passing. We propose a communication-aware framework where the probability of successful communication between connected devices is considered. Our analysis introduces the notion of the probabilistic optimality gap, highlighting its potential influence on determining the message-passing sequence based on the agent's broadcast reliability and strategic decisions regarding agents that can broadcast their messages multiple times in a resource-limited environment. This work not only contributes theoretical insights but also has practical implications for designing and analyzing decentralized systems in uncertain communication environments. A numerical example demonstrates the impact of our results.