# Submodular Optimization for Consensus Networks with Noise-Corrupted Leaders

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Dec 2017.

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

- [Delayed Verification Destabilizes Multi-Agent LLM Belief: Instability Thresholds and Optimal Corrector Placement](https://mlsanity.com/paper/2606.27409/) (2026)
- [How Much Does Correctness Cost? Budgeted Placement of Strong Correctors in a Weak Multi-Agent Swarm](https://mlsanity.com/paper/2607.09765/) (2026)

## Abstract (arXiv)

We consider the leader selection problem in a network with consensus dynamics where both leader and follower agents are subject to stochastic external disturbances. The performance of the system is quantified by the total steady-state variance of the node states, and the goal is to identify the set of leaders that minimizes this variance. We first show that this performance measure can be expressed as a submodular set function over the nodes in the network. We then use this result to analyze the performance of two greedy, polynomial-time algorithms for leader selection, showing that the leader sets produced by the greedy algorithms are within provable bounds of optimal.