AF: Small: New Perspectives on Special Methods for Graph Algorithms

许多重要图基元的经典算法是在传统的效率概念是多项式运行时间的时候设计的。 然而，今天的许多应用涉及由数百万甚至数十亿个节点组成的图。对于这些大量的输入，实用的算法必须在输入大小上尽可能接近线性的时间内运行。设计图算法的谱方法将实例图视为矩阵，并利用相应线性运算符的代数性质。最近，在这一领域的研究已经导致了许多基本的图形问题，如电力流，最大流和无向图的图分割的快速谱算法的设计。 这个项目的目标是开发一种新的算法方法，结合谱方法和从优化正则化的思想。 正则化是一种机制，用于修改给定的优化问题，使其更适合于已知的算法，而不改变其显着特征。令人惊讶的是，最近在快速谱算法设计方面的许多突破可以被视为应用不同类型的正则化。本研究旨在利用这种解释来设计更快，更简单的分析和更容易实现的算法。本研究的另一个目的是整合机器学习、统计学和凸优化中正则化的不同观点，在这些领域和算法设计之间建立新的桥梁。由于所考虑的图问题的实际重要性，本研究还将侧重于对所设计的算法进行经验评估。 这些评价将分发给相关受众，以最大限度地扩大该奖的影响。此外，由于该项目旨在开发算法设计中的新的基本技术，因此将特别努力将本研究的材料纳入PI的教学活动，并为公众准备教育材料。

Classical algorithms for many important graph primitives were designed at a time when the conventional notion of efficiency was polynomial running time. However, many of today's applications involve graphs consisting of millions, or even billions, of nodes. On these massive inputs, practical algorithms must run in time that is as close to linear as possible in the size of the input.The spectral approach to designing graph algorithms views the instance graph as a matrix and makes use of the algebraic properties of the corresponding linear operator. Recently, research in this area has led to the design of faster spectral algorithms for many essential graph problems, such as electrical flow, maximum flow and graph partitioning in undirected graphs. The goal of this project is to develop a novel algorithmic approach by combining spectral methods and the idea of regularization from optimization. Regularization is a mechanism for modifying a given optimization problem to make it more amenable to known algorithms without changing its salient characteristics. Surprisingly, many of the recent breakthroughs in the design of fast spectral algorithms can be viewed as applying different types of regularization. This research aims to exploit this interpretation to design algorithms that are faster, simpler to analyze and easier to implement. Another aim of this research is to integrate different perspectives on regularization from Machine Learning, Statistics and Convex Optimization, to create new bridges between these fields and the design of algorithms.Due to the practical importance of the graph problems under consideration, the work will also focus on empirically evaluating the algorithms designed. These evaluations will be disseminated to the relevant audiences to maximize the impact of the award. Moreover, because this project aims to develop new fundamental techniques in the design of algorithms, a particular effort will be devoted to incorporating material from this research into the PI's teaching activity and to preparing educational material for the public.