CAREER: Theory of 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.