Title:
Fast Approximation Algorithms and Complexity Analysis for Design of Networked Systems
Fast Approximation Algorithms and Complexity Analysis for Design of Networked Systems
Author(s)
Yi, Yuhao
Advisor(s)
Editor(s)
Collections
Supplementary to
Permanent Link
Abstract
This 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.
Sponsor
Date Issued
2019-11-18
Extent
57:21 minutes
Resource Type
Moving Image
Resource Subtype
Lecture