Strong Approximation Algorithms for the Steiner Tree Problem and Related Problems

Steiner树问题及相关问题的强逼近算法

• 批准号: 317997620
• 负责人: Professor Dr. Markus Chimani
• 金额: --
• 依托单位: Arbeitsgruppe Theoretische Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2016
• 资助国家: 德国
• 起止时间: 2015-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/317997620?language=en
• 关键词: Strong; Approximation; Algorithms; Steiner; Tree

We consider classical and practically relevant NP-hard problems in the area of topological network design. The probably best known such problem---besides the polynomial-time solvable spanning tree problem---is the Steiner tree problem: given a weighted graph, find a minimum-weight tree connecting a given set of terminal nodes. In practice, this and related problems arise in as diverse fields as, e.g., telecommunication networks, VLSI design, and geography.In previous studies, the theoretically strong approximation algorithms for the Steiner tree problem proved to be rather impractical due to their central concepts. The goal of this project is on the one hand to make these concepts more applicable in practice. On the other hand, we aim to develop new related but more directly applicable concepts that lead to similar quality guarantees.Apart from the classical Steiner tree problem, we also consider the problems of 2-connected network design, spanners, and directed Steiner trees, as well as practically relevant problems from geography/geoinformatic applications.

我们考虑了拓扑网络设计领域的经典和实际相关的np困难问题。除了多项式时间可解的生成树问题之外，最著名的问题可能是斯坦纳树问题：给定一个加权图，找到一个连接给定终端节点集的最小权值树。在实践中，这个和相关的问题出现在不同的领域，例如，电信网络，超大规模集成电路设计和地理。在以往的研究中，对于Steiner树问题，理论上强逼近算法由于其中心概念而被证明是相当不切实际的。这个项目的目标一方面是使这些概念在实践中更适用。另一方面，我们的目标是开发新的相关但更直接适用的概念，从而实现类似的质量保证。除了经典的斯坦纳树问题外，我们还考虑了2连通网络设计、扳手和有向斯坦纳树的问题，以及地理/地理信息学应用中的实际相关问题。

项目成果

Strong Steiner Tree Approximations in Practice

实践中的强斯坦纳树近似

• DOI: 10.1145/3299903
• 发表时间: 2019
• 期刊: Journal of Experimental Algorithmics (JEA)
• 作者: S. Beyer;M. Chimani
• 通讯作者: M. Chimani