# On the Complexity of Minimum-Cost Networked Estimation of Self-Damped Dynamical Systems

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2019.

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

- [Integrating LLMs with ITS: Recent Advances, Potentials, Challenges, and Future Directions](https://mlsanity.com/paper/2501.04437/) (2025)
- [Dyn-Backdoor: Backdoor Attack on Dynamic Link Prediction](https://mlsanity.com/paper/2110.03875/) (2021)

## Abstract (arXiv)

In this paper, we consider the optimal design of networked estimators to minimize the communication/measurement cost under the networked observability constraint. This problem is known as the minimum-cost networked estimation problem, which is generally claimed to be NP-hard. The main contribution of this work is to provide a polynomial-order solution for this problem under the constraint that the underlying dynamical system is self-damped. Using structural analysis, we subdivide the main problem into two NP-hard subproblems known as (i) optimal sensor selection, and (ii) minimum-cost communication network. For self-damped dynamical systems, we provide a polynomial-order solution for subproblem (i). Further, we show that the subproblem (ii) is of polynomial-order complexity if the links in the communication network are bidirectional. We provide an illustrative example to explain the methodologies.