Yuhao Yi - Fast Approximation Algorithms and Complexity Analysis for Design of Networked Systems
From Katie Gentilello
This talk focuses on network design algorithms for optimizing average consensus dynamics, dynamics that are widely used for information diﬀusion 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 ﬁrst 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 ﬁt into context and also propose some ideas for future work.