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