Fast Approximation Algorithms and Complexity Analysis for Design of Networked Systems

Presented on November 18, 2019 at 11:00 a.m. in the Klaus Advanced Computing Building, Room 1116E.Yuhao Yi is a postdoctoral researcher in Computer Science at Rensselaer Polytechnic Institute (RPI). His research interests include network science, distributed control, and spectral graph theory.Runtime: 57:21 minutesThis talk focuses on network design algorithms for optimizing average consensus dynamics, dynamics that are widely used for information diffusion and distributed coordination in networked control systems. Network design algorithms seek to modify the network to improve the performance of the dynamical system. This can be achieved by controlling a subset of vertices or adding/removing edges in the network. We provide new algorithmic and hardness results for two network design problems. The first problem is selecting at most k vertices as leaders so as to minimize the steady-state variance of the system. We prove the NP-hardness of the problem, and propose a greedy algorithm with an approximation factor arbitrarily close to (1- k/(k-1) 1/e), which runs in nearly-linear time of km, where m is the number of edges. The second problem is adding at most k edges from a candidate edge set to minimize network entropy. This problem is equivalent to maximizing the log number of spanning trees in a connected graph. We propose an algorithm that runs in nearly-linear time of m with an approximation factor arbitrarily close to (1-1/e), and we prove hardness of approximation of the problem. Finally, we summarize algorithmic and complexity results related to network design and discuss how our methods fit into context and also propose some ideas for future work