AF: Small: New Algorithmic Primitives for Directed Graphs: Sparsification and Preconditioning

AF：小：有向图的新算法基元：稀疏化和预处理

• 批准号: 1718533
• 负责人: Yang Peng
• 金额: $ 45万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1718533&HistoricalAwards=false
• 关键词: AF; Small; New; Algorithmic; Primitives

Many real-life problems arising from social networks, transportation, image processing, resource assignment and other domains use graphs as a fundamental underlying structure for modeling and solving problems. Graphs and networks are widely used formats for representing data via edges that describe pairs of related objects. There is a growing need for efficient graph algorithms due to the abundance of large graphs in many of these domains. This project will study two important tools in the development of efficient graph algorithms: sparsification, which removes edges while preserving the overall structure of the graph, and preconditioned iterative methods, which improve the qualities of solutions. It will also support the development of courses that incorporate experimental aspects motivated by data science, the training of research-oriented students, and outreach activities based on algorithmic problem solving. The goal of this project is to extend key primitives for efficient algorithms on undirected graphs to directed graphs. Recent works hinted that two important tools for designing provably efficient algorithms on undirected graphs, sparsification and preconditioning, can be generalized to directed graphs when used in conjunction with each other. Studying these routines together enables a greater range of algorithmic flexibility: the construction of approximate graphs now only need to preserve solutions relevant to the convergence of the other loop, instead of for all possible inputs. The project will focus on extending this interplay between sparsification and preconditioning through better understanding of the underlying tools, iterative methods and concentration bounds. Progress on these tools can in turn lead to improvements on fundamental problems in graph algorithms such as computing directed random walks, finding maximum matchings on dense bipartite graphs, and maintaining large matchings on dynamically changing graphs.

社会网络、交通运输、图像处理、资源分配等领域中的许多现实问题都使用图作为建模和解决问题的基本底层结构。图和网络是广泛使用的格式，用于通过描述相关对象对的边来表示数据。由于在许多这样的领域中存在大量的大图，因此对高效图算法的需求日益增长。这个项目将研究开发高效图算法的两个重要工具：稀疏化，它在保持图的整体结构的同时去除边，以及预条件迭代方法，它可以提高解的质量。它还将支持开发包含以数据科学为动力的实验方面的课程，培训注重研究的学生，以及以解决算法问题为基础的外联活动。这个项目的目标是将无向图上高效算法的关键原语扩展到有向图。最近的工作表明，在无向图上设计可证明有效的算法的两个重要工具--稀疏化和预条件，当它们结合使用时可以推广到有向图。同时研究这些例程可以实现更大范围的算法灵活性：构建近似图现在只需要保留与另一个循环的收敛相关的解，而不是所有可能的输入。该项目将专注于通过更好地了解基本工具、迭代方法和浓度界限来扩展稀疏化和预处理之间的这种相互作用。这些工具的进步反过来可以导致图算法中基本问题的改进，如计算有向随机游走、在密集二部图上寻找最大匹配以及在动态变化的图上保持大匹配。

项目成果

Expander Decomposition and Pruning: Faster, Stronger, and Simpler

• DOI: 10.1137/1.9781611975482.162
• 发表时间: 2018-12
• 作者: Thatchaphol Saranurak;Di Wang

Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs

中等密集图上近线性时间的二分匹配

• DOI: 10.1109/focs46700.2020.00090
• 发表时间: 2020
• 作者: van den Brand, Jan;Lee, Yin-Tat;Nanongkai, Danupon;Peng, Richard;Saranurak, Thatchaphol;Sidford, Aaron;Song, Zhao;Wang, Di
• 通讯作者: Wang, Di

Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions

• DOI: 10.1109/focs.2018.00042
• 发表时间: 2018-05
• 期刊: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: T. Chu;Yu Gao;Richard Peng;Sushant Sachdeva;Saurabh Sawlani;Junxing Wang

Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

• DOI: 10.1109/focs.2017.90
• 发表时间: 2017-05
• 期刊: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: D. Durfee;John Peebles;Richard Peng;Anup B. Rao

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond

用于平衡切割的确定性算法及其在动态连接、流等方面的应用

• DOI: 10.1109/focs46700.2020.00111
• 发表时间: 2020
• 作者: Chuzhoy, Julia;Gao, Yu;Li, Jason;Nanongkai, Danupon;Peng, Richard;Saranurak, Thatchaphol
• 通讯作者: Saranurak, Thatchaphol