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

AF：小：算法：线性、谱和近似。

• 批准号: 1118083
• 负责人: Satish Rao
• 金额: $ 35万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1118083&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Linear; Spectral

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.

PI 将研究并尝试提高算法基本领域的最新技术：线性方程组、匹配和近似的线性时间解。 线性系统工作的基础是 Spielman 和 Teng 最近的突破性工作以及 Koutis、Miller 和 Peng 的后续工作，他们为求解一大类线性系统提供了非常有效的、接近线性时间的算法。该方案的思想与 PI 长期研究的图划分和度量近似交织在一起。 PI 还将利用 Spielman 和 Teng 的想法来解决匹配或分配问题；特别是，从匹配问题的角度理解图稀疏化技术。最后，研究人员建议致力于扩展最近在 TSP 问题上的突破，将问题的非对称版本简化为找到一棵可以方便地交叉切割的树。线性系统的解决方案是各种工程和科学的核心问题范围从气候变化到建筑建模，再​​到喷气发动机设计（本质上是任何涉及模拟经典物理的问题）。 PI 建议研究的分配问题是许多生产和业务应用程序的核心：实际上，几乎所有能够有效地将作业分配给任务的应用程序。最后，TSP 问题是一个著名的有趣问题，无论是其本身还是其研究通常带来的方法论突破都值得研究。