# A Randomized Greedy Algorithm for Near-Optimal Sensor Scheduling in Large-Scale Sensor Networks

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

## Key facts

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

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

- [Demarcating Endogenous and Exogenous Opinion Dynamics: An Experimental Design Approach](https://mlsanity.com/paper/2102.05954/) (2021)
- [Localized Distributional Robustness in Submodular Multi-Task Subset Selection](https://mlsanity.com/paper/2404.03759/) (2024)
- [Submodular Maximization Approaches for Equitable Client Selection in Federated Learning](https://mlsanity.com/paper/2408.13683/) (2024)
- [Belief-Conditioned One-Step Diffusion: Real-Time Trajectory Planning with Just-Enough Sensing](https://mlsanity.com/paper/2508.12166/) (2025)
- [Simultaneous Perception-Action Design via Invariant Finite Belief Sets](https://mlsanity.com/paper/2109.05073/) (2021)

## Abstract (arXiv)

We study the problem of scheduling sensors in a resource-constrained linear dynamical system, where the objective is to select a small subset of sensors from a large network to perform the state estimation task. We formulate this problem as the maximization of a monotone set function under a matroid constraint. We propose a randomized greedy algorithm that is significantly faster than state-of-the-art methods. By introducing the notion of curvature which quantifies how close a function is to being submodular, we analyze the performance of the proposed algorithm and find a bound on the expected mean square error (MSE) of the estimator that uses the selected sensors in terms of the optimal MSE. Moreover, we derive a probabilistic bound on the curvature for the scenario wherecolorblack the measurements are i.i.d. random vectors with bounded ℓ2 norm. Simulation results demonstrate efficacy of the randomized greedy algorithm in a comparison with greedy and semidefinite programming relaxation methods.