Optimal k-Leader Selection for Coherence and Convergence Rate in One-Dimensional Networks

DOI10.1109/TCNS.2016.2520201MaRDI QIDQ6272858arXivFDO

Authors Stacy Patterson, Neil McGlohon, K. Dyagilev

Publication date 24 April 2016

Published in arXiv

Full work available at URL https://doi.org/10.1109/TCNS.2016.2520201

Mathematics Subject Classification ID

Applications of graph theory (05C90) Hierarchical systems (93A13) Networked control (93B70) Consensus (93D50)

arXiv classification

cs.SYmath.OC

Abstract: We study the problem of optimal leader selection in consensus networks under two performance measures (1) formation coherence when subject to additive perturbations, as quantified by the steady-state variance of the deviation from the desired trajectory, and (2) convergence rate to a consensus value. The objective is to identify the set of $k$ leaders that optimizes the chosen performance measure. In both cases, an optimal leader set can be found by an exhaustive search over all possible leader sets; however, this approach is not scalable to large networks. In recent years, several works have proposed approximation algorithms to the $k$-leader selection problem, yet the question of whether there exists an efficient, non-combinatorial method to identify the optimal leader set remains open. This work takes a first step towards answering this question. We show that, in one-dimensional weighted graphs, namely path graphs and ring graphs, the $k$-leader selection problem can be solved in polynomial time (in both $k$ and the network size $n$). We give an $O(n^3)$ solution for optimal $k$-leader selection in path graphs and an $O(k{n}^3)$ solution for optimal $k$-leader selection in ring graphs.

This page was built for publication: Optimal k-Leader Selection for Coherence and Convergence Rate in One-Dimensional Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6272858)