AF: Small: Algorithms: Linear, Spectral, and Approximation.

PI将研究并尝试改进算法基本领域的最新技术：线性方程组的线性时间解、匹配和近似。线性系统工作的基础是Spielman和Teng最近的突破性工作以及Koutis、Miller和Peng的后续工作，他们给出了求解一大类线性系统的非常有效的近线性时间算法。该方案的思想与PI长期研究的图划分和度量近似相互交织在一起。PI还将使用Spielman和Teng的想法来攻击匹配或分配问题；特别是从匹配问题的角度理解图稀疏技术。最后，研究人员建议扩展在TSP问题上的最新突破，该突破将问题的不对称版本简化为找到一棵横切的树。线性系统的解决方案是从气候变化、建筑建模到喷气发动机设计(基本上任何与模拟经典物理有关的问题)的各种工程和科学问题的核心。PI建议调查的分配问题是许多生产和商业应用程序的核心：事实上，几乎任何有效地将作业分配给任务的应用程序。最后，TSP问题是一个著名的耐人寻味的问题，值得研究，因为它本身以及它的研究通常导致的方法论突破。

The PI will study and attempt to improve the state of the art in fundamental areas of algorithms: linear time solution of systems of linear equations, matchings, and approximation. The basis of the linear system work is the recent breakthrough work of Spielman and Teng and the follow up work of Koutis, Miller, and Peng, who gave very efficient, near linear time algorithms for solving a large class of linear systems. The ideas in this scheme are intertwined with graph partitioning and metric approximation which the PI has long researched. The PI will also use ideas from Spielman and Teng to attack the matching or assignment problem; in particular, understanding graph sparsification techniques in terms of the matching problem. Finally, the investigator proposes to work on extending a recent breakthrough on the TSP problem that reduced the asymmetric version of the problem to one of finding a tree that crosses cuts expediently.The solution of linear systems is central to a tremendous variety of engineering and scientific problems ranging from climate change, to building modeling, to jet engine design (essentially any problem dealing with simulating classical physics). The assignment problem which the PI proposes to investigate is central in numerous production and business applications: indeed, almost any application that assigns jobs to tasks efficiently. Finally, the TSP problem is a famously intriguing problem which is worth studying for its own sake and for the methodogical breakthroughs that its study typically leads to.