CAREER: Optimization Models and Approximation Algorithms for Network Vulnerability and Adaptability

点击翻译按钮获取中文摘要

Complex network systems are extremely vulnerable. This vulnerability may be propagated, leading to a much more devastating consequence. Furthermore, several network algorithms must be adaptable to changes in order to maintain their functions. In the presence of uncertainty, network vulnerability and adaptability are the two major aspects that must be deeply investigated.This proposal is using optimization theory and approximation techniques to address the following fundamental questions: How do we quantitatively measure the vulnerability degree of the network? How is the vulnerability propagated? What are the quantitative benefits of using adaptive solutions vs. re-computing it from scratch? What techniques can we use for adaptive solutions in order to theoretically bound their performance? The proposal provides several new theoretical frameworks and approximation techniques to characterize the network vulnerability and adaptability, which brings the understanding of network vulnerability and adaptability to the next level.This research can potentially impact nearly all applications that benefit from networks such as the Internet, critical network infrastructures, and transportation networks where vulnerability and adaptability are important characteristics. In addition to its obvious impact on networks, the project crosses several research areas such as graph theory, approximation algorithms, combinatorial optimization, and computational complexity, thus it has a profound impact on the theory of optimization and approximation, especially the adaptive approximation techniques.