CAREER: Theory of Fast Graph Optimization

职业：快速图优化理论

• 批准号: 1844855
• 负责人: Aaron Sidford
• 金额: $ 55万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-02-01 至 2025-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1844855&HistoricalAwards=false
• 关键词: CAREER; Theory; Fast; Graph; Optimization

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.

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

项目成果

Dynamic Maxflow via Dynamic Interior Point Methods

• DOI: 10.1145/3564246.3585135
• 发表时间: 2022-12
• 期刊: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
• 作者: Jan van den Brand;Y. Liu;Aaron Sidford

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

次多项式更新时间内无向图的增量近似最大流

• 发表时间: 2024
• 期刊: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
• 作者: van den Brand, Jan;Chen, Li;Kyng, Rasmus;Liu, Yang P.;Peng, Richard;Probst Gutenberg, Maximilian;Sachdeva, Sushant;Sidford, Aaron
• 通讯作者: Sidford, Aaron

Faster maxflow via improved dynamic spectral vertex sparsifiers

通过改进的动态光谱顶点稀疏器加快最大流速度

• DOI: 10.1145/3519935.3520068
• 发表时间: 2022
• 期刊: 54th ACM Symposium on Theory of Computing
• 作者: van den Brand, Jan;Gao, Yu;Jambulapati, Arun;Lee, Yin Tat;Liu, Yang P.;Peng, Richard;Sidford, Aaron
• 通讯作者: Sidford, Aaron

Memory-sample tradeoffs for linear regression with small error

• DOI: 10.1145/3313276.3316403
• 发表时间: 2019-04
• 期刊: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Vatsal Sharan;Aaron Sidford;G. Valiant

Near-optimal Approximate Discrete and Continuous Submodular Function Minimization

近最优近似离散和连续子模函数最小化

• DOI: 10.1137/1.9781611975994.51
• 发表时间: 2020
• 期刊: Symposium on Discrete Algorithms
• 作者: Axelrod, Brian;Liu, Yang P.;Sidford, Aaron
• 通讯作者: Sidford, Aaron