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) 大型网络的高效算法设计，重点关注基本图优化问题的近似和效率之间的权衡。该项目将集成组合优化、概率论、数学规划和连续优化等不同领域的工具来建模和解决这些算法问题，预计该项目也将为这些领域的相关问题提供新的思路。