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.