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

点击翻译按钮获取中文摘要

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.