权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CAREER: New Directions in Graph Algorithms

职业：图算法的新方向

基本信息

批准号：
1750140
负责人：
Debmalya Panigrahi
金额：
$ 51.6万
依托单位：
Duke University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-02-01 至 2024-01-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750140&HistoricalAwards=false
关键词：
CAREER New Directions Graph Algorithms

项目摘要

Networks such as the Internet, social networks, transportation maps, and communication backbones have an ubiquitous presence in modern life. Graph algorithms play a crucial role in these networks by providing a range of basic services such as navigation, traffic management, and robustness against physical failures. Moreover, graphs are useful in modeling interactions in a variety of systems that arise in physical, biological, and social sciences. This project identifies a set of common themes in the algorithmic challenges that arise in modern networks -- uncertainty of data, complex failure patterns, and gigantic scale -- and seeks generic solutions that address these core issues. The project is expected to provide new insights into classical graph optimization problems, while also creating new models, problem formulations, and research directions that embrace these broad challenges. This project will also train graduate and undergraduate researchers in theoretical computer science, with an emphasis on gender diversity and participation of underrepresented groups. For over fifty years, graph algorithms have played a central role in the advancement of computer science, both in theory and practice. Modern networks have evolved in scale, structure, and functionality, inspiring new models, problems, and algorithms. This project focuses on three key research thrusts for modern graph algorithms: (a) network design under unreliable or imprecise future predictions, by developing generic optimization techniques for uncertain and dynamic inputs; (b) the analysis of correlation effects in network failures by expanding the scope of classical metrics like minimum cuts to incorporate correlated failures of multiple network components; and (c) the design of highly efficient algorithms for large networks, focusing on the tradeoff between approximation and efficiency for fundamental graph optimization problems. The project will integrate tools from diverse areas such as combinatorial optimization, probability theory, mathematical programming, and continuous optimization to model and address these algorithmic questions, and the project is expected to shed new light on related questions in these domains as well.

诸如互联网、社交网络、交通地图和通信骨干网的网络在现代生活中无处不在。图算法在这些网络中发挥着至关重要的作用，提供了一系列基本服务，如导航，流量管理和对物理故障的鲁棒性。此外，图形在物理、生物和社会科学中出现的各种系统中的交互建模中非常有用。该项目确定了现代网络中出现的算法挑战中的一组共同主题-数据的不确定性，复杂的故障模式和巨大的规模-并寻求解决这些核心问题的通用解决方案。该项目预计将为经典图优化问题提供新的见解，同时还将创建新的模型，问题公式和研究方向，以迎接这些广泛的挑战。该项目还将培训理论计算机科学的研究生和本科生研究人员，重点是性别多样性和代表性不足群体的参与。五十多年来，图算法在计算机科学的发展中发挥了核心作用，无论是在理论上还是在实践中。现代网络在规模、结构和功能上都发生了变化，激发了新的模型、问题和算法。该项目侧重于现代图算法的三个关键研究方向：（a）通过开发不确定和动态输入的通用优化技术，在不可靠或不精确的未来预测下进行网络设计;（B）通过扩展经典度量（如最小割）的范围，将多个网络组件的相关故障纳入其中，分析网络故障中的相关效应;以及（c）设计用于大型网络的高效算法，集中于基本图优化问题的近似和效率之间的权衡。该项目将整合来自不同领域的工具，如组合优化，概率论，数学规划和连续优化，以建模和解决这些算法问题，预计该项目也将为这些领域的相关问题提供新的思路。