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将研究并尝试改进算法基本领域的最新技术：线性方程组的线性时间解，匹配和近似。 的基础上的线性系统的工作是最近的突破性工作斯皮尔曼和滕和后续工作的Koutis，米勒，彭，谁给了非常有效的，近线性时间算法解决了一大类线性系统。该方案中的思想与PI长期研究的图划分和度量近似交织在一起。 PI还将使用Spielman和Teng的思想来解决匹配或分配问题;特别是，从匹配问题的角度理解图稀疏化技术。最后，研究人员建议扩展最近在TSP问题上的突破，将问题的非对称版本简化为找到一个方便地穿过切割的树。线性系统的解决方案是各种工程和科学问题的核心，从气候变化到建筑建模，再到喷气发动机设计（基本上是任何处理模拟经典物理的问题）。PI提出要研究的分配问题是许多生产和商业应用程序的核心：事实上，几乎所有有效地将作业分配给任务的应用程序都是如此。最后，TSP问题是一个著名的有趣的问题，值得研究，因为它本身和它的研究通常会导致方法上的突破。