*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Yuhao Yi (RPI)
Monday, November 18, 2019
Klaus 1116 East- 11:00 am
Title: Fast Approximation Algorithms and Complexity Analysis for Design of Networked Systems
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.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
