AF: Small: Efficient Approximations for Dynamic Programs and Other Topics in Algorithms

该项目支持新的和正在进行的研究在算法和计算复杂性的几个主题。 该项目的一个主要重点将是某些组合优化问题，如确定两个数据序列的最长公共子序列，可以制定为特殊网络中的最短路径问题。 我们的目标是开发算法，可证明给正确答案的近似值，并显着快于现有的算法。 该项目的另一个目标是为网络构建稀疏空间，这些网络是具有很少边缘的子网络，这些边缘保留（部分或近似）原始网络的连通性或距离属性。 该项目的第三部分将寻求建立MapReduce范式中并行程序效率的固有限制，MapReduce范式是一种越来越流行的并行编程范式，其中计算发生在一系列精确定义的轮次中。 我们的目的是通过证明某些基本计算任务所需的计算轮数的下限来建立此模型的一些固有限制。 该项目的另一部分将开发新的算法，并确定文件维护问题的效率限制，其中数字以在线方式呈现并加载到线性数组中（项目之间可能有间隙），以便项目的从左到右顺序与自然顺序相匹配。成本是通过在装载过程中移动任何物品的总次数来衡量的。 该奖项旨在通过随机化获得比现有算法更好的算法，或者证明随机化不能显著改善现有最佳算法。通过推进算法和复杂性理论，该奖项将增加有效设计算法的工具集。 为有效估计动态程序而开发的算法技术对于开发用于诸如字符串匹配之类的问题的算法的从业者可能是有用的，字符串匹配是在诸如生物数据的数据检索和分析之类的不同领域中出现的基本问题。 建立解决各种问题的计算资源的内在要求，可以指导相关问题的改进算法的搜索。 该项目的一个重要部分是培训研究生在该领域进行研究。

This project supports new and ongoing research on several topics in algorithms and computational complexity. A major focus of the project will be certain combinatorical optimization problems, such as determining the longest common subsequence of two data sequences, that can be formulated as shortest path problems in special networks. The goal is to develop algorithms that provably give close approximations to the correct answer and are significantly faster than existing algorithms. Another goal of the project is to construct sparse spanners for networks, which are subnetworks with few edges that preserve (partially or approximately) the connectivity or distance properties of the original network. A third part of the project will seek to establish inherent limitations on the efficiency of parallel programs in the MapReduce paradigm, which is an increasingly popular paradigm for parallel programming in which computation occurs in a sequence of precisely defined rounds. The aim is to establish some inherent limitations on this model by proving lower bounds on the number of computation rounds needed for certain basic computational tasks. Another part of the project will develop new algorithms and determine limits to efficiency for the file maintenance problem, in which numbers are presented in an online manner and are loaded into a linear array (possibly with gaps between items) so that the left-to-right order of the items matches the natural order. The cost is measured by the total number of times any item is moved during the loading process. The aim here is to obtain better algorithms than the existing ones using randomization, or to establish that randomization can not significantly improve on the best existing algorithms.By advancing the theory of algorithms and complexity, this award will increase the set of tools available for efficient design of algorithms. The algorithmic techniques developed for efficient estimation of dynamic programs may be useful for practitioners developing algorithms for problems such as string matching, which is a fundamental problem that arises in varied areas such as data retrieval and analysis of biological data. Establishing inherent requirements on computational resources for solving various problems can guide the search for improved algorithms for related problems. An important part of the project is the training of graduate students to do research in the field.