Foundations of work-efficient constant-time parallel dynamic and static algorithms

高效工作的恒定时间并行动态和静态算法的基础

• 批准号: 523044065
• 负责人: Professor Dr. Thomas Schwentick
• 金额: --
• 依托单位: Informatik I - Lehrstuhl Logik in der Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/523044065?language=en
• 关键词: Foundations; work; efficient; constant; time

The project aims to extend the research in Dynamic Complexity Theory by the aspect of work-efficiency and thus build a bridge to the rich research area of Dynamic Algorithms. Recent research in Dynamic Complexity Theory has identified many algorithmic problems that can be maintained by dynamic parallel algorithms with only constant time on the Parallel Random Access Model (PRAM), independent of the size of inputs. As an example, it has been shown that the reachability problem for directed graphs can be maintained by such algorithms under edge insertions and edge deletions. However, this research has focussed solely on the constant-time aspect and has ignored other aspects of efficiency, most notably the work, i.e. the overall number of steps summed over all processors. As a result, the amount of work needed by the algorithms in the literature is a serious obstacle to their practical usefulness. The main goal of this project is to design work-efficient constant-time parallel dynamic algorithms for important algorithmic problems and to develop versatile algorithmic techniques. A closely related additional goal is to design work-efficient constant-time parallel static algorithms, in particular for sub-tasks of dynamic algorithms. Complementary investigations will try to identify barriers for the existence and work-efficieny of both kinds of algorithms and to design a language by which such dynamic algorithms can be specified.

该项目旨在从工作效率方面扩展动态复杂性理论的研究，从而为动态算法的丰富研究领域架起一座桥梁。动态复杂性理论的最新研究已经确定了许多算法问题，这些问题可以通过动态并行算法在并行随机访问模型（PRAM）上仅用恒定时间来维护，而与输入的大小无关。作为一个例子，已经表明有向图的可达性问题可以通过这样的算法在边插入和边删除下维持。然而，这项研究仅关注恒定时间方面，而忽略了效率的其他方面，最值得注意的是工作，即所有处理器上总的步骤总数。因此，文献中的算法所需的工作量严重阻碍了它们的实际用途。该项目的主要目标是为重要的算法问题设计工作高效的恒定时间并行动态算法，并开发通用的算法技术。一个密切相关的附加目标是设计工作高效的恒定时间并行静态算法，特别是对于动态算法的子任务。补充研究将尝试找出两种算法的存在和工作效率的障碍，并设计一种可以指定此类动态算法的语言。