CAREER: Geometric Techniques for Algorithm Design

职业：算法设计的几何技术

• 批准号: 0843915
• 负责人: Jonathan Kelner
• 金额: $ 35.7万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0843915&HistoricalAwards=false
• 关键词: CAREER; Geometric; Techniques; Algorithm; Design

This project focuses on the application of geometric and analytic techniques from pure mathematics to the study of fundamental questions in the theory of algorithms.The principal investigator aims to develop two sets of mathematical tools and their applications to algorithm design: integral geometry and spectral/differential graph theory. In the former, he aims to study the use of geometric concepts such as lengths and volumes in configuration spaces to understand the complexity of combinatorial algorithms and the diameters of polytope graphs. In the latter, he proposes to work on understanding the right way to employ structures on graphs analogous to those of continuous differential geometry and harmonic analysis, such Laplacians, Green's functions, Hodge structures, and connections.The principal investigator intends to apply these techniques to a variety of algorithmic pursuits, including:* the search for a strongly polynomial time algorithm for linear programming;* new algorithms for nonconvex optimization;* a faster algorithm for finding (1+epsilon)-approximate maximum flows in undirected graphs;* the development of a general set of tools for designing nearly linear time graph algorithms; and* distributed routing protocols and other decentralized and local graph algorithms.In addition to advancing the theoretical study of several central questions in the theory of algorithms, this research holds the potential for broad practical impact. In recent years, it has increasingly become the case that much of the world can be effectively modeled by very large graphs, whether they be interconnected computers, social networks, or collections of roads. These graphs are often so large that even a quadratic algorithm would be impractically slow. For this reason, effective tools for designing algorithms that run in nearly linear time are becoming more and more important. In addition, there is an increasing focus now on having collections of loosely coordinated computers work together to solve large algorithmic tasks. In both cases, the development of spectral/differential graph theory holds great promise. Differential geometry and the analogous discrete theory that the principal investigator intends to develop aim to synthesize pieces of local information to deduce global properties. As such, spectral and differential graph theory provide a general approach to developing both nearly-linear time algorithms and distributed ones. Furthermore, linear programming is applied to solve a vast array of practical problems in a wide variety of fields, inclding economics, operations research, combinatorial optimization, and logistics. Any algorithmic improvement for it would broaden the set of such problems that can be practically solved.

本项目的重点是将纯数学中的几何和分析技术应用于算法理论中的基本问题的研究。主要研究者的目标是开发两套数学工具及其在算法设计中的应用：积分几何和谱/微分图论。 在前者中，他的目标是研究几何概念的使用，如配置空间中的长度和体积，以了解组合算法的复杂性和多面体图的直径。 在后者中，他提出了理解正确的方式来使用类似于连续微分几何和调和分析的结构，如拉普拉斯算子，绿色函数，霍奇结构和连接。首席研究员打算将这些技术应用于各种算法的追求，包括：* 寻找线性规划的强多项式时间算法;* 非凸优化的新算法;* 一个更快的算法找到（1+ 1）-近似最大流在无向图;* 一套通用工具的开发，设计近线性时间图算法;和 * 分布式路由协议和其他分散和本地graph algorithm.In除了推进算法理论中的几个中心问题的理论研究，这项研究具有广泛的实际影响的潜力。 近年来，越来越多的情况是，世界上的许多地方都可以通过非常大的图来有效地建模，无论它们是互连的计算机、社交网络还是道路的集合。这些图往往是如此之大，即使是二次算法将是不切实际的慢。因此，设计在近似线性时间内运行的算法的有效工具变得越来越重要。此外，现在越来越关注让松散协调的计算机集合一起工作来解决大型算法任务。在这两种情况下，谱/微分图论的发展都有很大的希望。微分几何和类似的离散理论，主要研究者打算发展的目的是综合片的局部信息，以推断全球的性质。 因此，谱和微分图论提供了一种通用的方法来开发近线性时间算法和分布式算法。 此外，线性规划被应用于解决各种领域的大量实际问题，包括经济学，运筹学，组合优化和物流。 对它的任何算法改进都将扩大可以实际解决的这类问题的集合。