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）针对大型网络的高效算法的设计，重点是基本图优化问题的近似和效率之间的权衡。该项目将整合来自组合优化，概率理论，数学编程和连续优化等不同领域的工具，以建模和解决这些算法问题，并且预计该项目也将为这些领域中的相关问题提供新的启示。