CAREER: Theory of Fast Graph Optimization

图是用于对复杂的、高度互连的数据进行建模的最基本的数学抽象之一。无论是安排航班、在社交网络中寻找社区、路由互联网流量、构建深度网络，还是简单地可视化大型数据集，图表都是用于执行这些操作的重要工具。因此，高效的图优化算法是非常令人垂涎的，并且图优化问题是计算机科学、运筹学、数值分析和科学计算的理论和实践中研究最充分的问题之一。最近的数据集大小的快速增长，进一步提高了对图算法的需求，可以扩展到接近最佳。然而，尽管经过了数十年的广泛研究，获得这样的算法仍然是一个非常开放且极具挑战性的问题。该项目的目标是直接解决这些开放问题，并提供一个广泛的图形优化工具包，以推动更快算法的开发。该项目将提供可证明的更快的图形算法，更好的图形结构结果，新的优化方法和多样化的教育材料。这项工作将被广泛使用，以促进节省时间，精力和宝贵的资源，为整个社会。该项目将专注于提供可证明更快的算法来解决一系列基本的，规范的和普遍的图优化问题，包括最大流问题，Perron向量计算和解决马尔可夫决策过程。这些都是经过充分研究的问题，在历史上一直是通往更广泛算法进步的垫脚石。为了克服高效图优化的历史障碍，该项目将利用来自多个社区的技术，包括运筹学的连续优化技术，数值分析的随机线性代数技术，以及理论计算机科学的组合优化技术。这三个学科和研究社区中的每一个都为图优化带来了不同的视角，该项目将改进每个领域的现有成果，并将它们统一起来，以创建更快的算法和更全面、更多样化的算法和优化教育方法。该奖项反映了NSF的法定使命，并通过利用基金会的知识价值和更广泛的影响进行评估，被认为值得支持审查标准。

Graphs are one of the most fundamental mathematical abstractions used to model complex, highly-interconnected data. Whether scheduling airline flights, finding communities in social networks, routing internet traffic, architecting a deep network, or simply visualizing a large data set, graphs are essential tools used to perform these operations. Consequently, efficient graph-optimization algorithms are highly coveted, and graph-optimization problems are among the most well-studied problems across the theory and practice of computer science, operations research, numerical analysis, and scientific computing. Recent rapid growth of data set sizes has further elevated the demand for graph algorithms which can scale nearly optimally. However, despite decades of extensive research, obtaining such algorithms is a wide-open and extremely challenging problem. The goal of this project is to directly address these open problems and provide a broad graph-optimization toolkit to fuel the development of faster algorithms. This project will provide provably faster graph algorithms, better structural results about graphs, new optimization methods, and diverse educational material. This work will be made widely accessible to facilitate savings in time, energy, and valued resources to society at large. This project will focus on providing provably faster algorithms for solving a range of fundamental, canonical, and pervasive graph-optimization problems, including the maximum-flow problem, Perron vector computation, and solving Markov decision processes. These are very well-studied problems that have historically served as a stepping stone towards broader algorithmic advances. To overcome historical barriers to efficient graph optimization, this project will leverage techniques from multiple communities, including continuous optimization techniques from operations research, randomized linear-algebra techniques from numerical analysis, and combinatorial optimization techniques from theoretical computer science. Each of these three disciplines and research communities brings a different perspective on graph optimization, and this project will improve upon existing results from each area and unify them to create faster algorithms and a more comprehensive and diverse approach to algorithm and optimization education.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.