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.