CAREER: New Directions in Graph Algorithms

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

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.