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

职业：网络脆弱性和适应性的优化模型和近似算法

基本信息

批准号：
0953284
负责人：
My Thai
金额：
$ 40万
依托单位：
University of Florida
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2010
资助国家：
美国
起止时间：
2010-02-15 至 2016-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=0953284&HistoricalAwards=false
关键词：
CAREER Optimization Models Approximation Algorithms

项目摘要

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.

复杂的网络系统非常脆弱。这种脆弱性可能会传播，从而导致更具毁灭性的后果。此外，几种网络算法必须适应更改，以维持其功能。在存在不确定性的情况下，网络脆弱性和适应性是必须深入研究的两个主要方面。该提案正在使用优化理论和近似技术来解决以下基本问题：我们如何定量衡量网络的脆弱性程度？脆弱性如何传播？使用自适应解决方案与从头开始重新计算的定量好处是什么？为了理论上绑定其性能，我们可以使用哪些技术用于自适应解决方案？该提案提供了几种新的理论框架和近似技术来表征网络漏洞和适应性，从而将网络漏洞和适应性的理解带入了下一个级别。这项研究可能会影响几乎所有受益于互联网，关键网络基础设施以及脆弱性网络等网络的应用程序。除了对网络的明显影响外，该项目还跨越了几个研究领域，例如图理论，近似算法，组合优化和计算复杂性，因此它对优化和近似理论具有深远的影响，尤其是自适应近似技术。