论文标题
在近似统一的成本距离坦Steiner树问题上进一步改进
Further Improvements on Approximating the Uniform Cost-Distance Steiner Tree Problem
论文作者
论文摘要
在本文中，我们考虑了公制空间中统一的成本距离坦Steiner树问题，这是众所周知的Steiner树问题的概括。成本距离的坦Steiner树将总长度和加权路径长度的总和从专用根到其他端子的总和，这些端子具有惩罚路径长度的重量。当树的意图用于信号传输时，它们将应用它们，例如在芯片设计或电信网络中，除总长度外，还必须考虑通过树的信号速度。自从Meyerson，Munagala和Plotkin首次提及该问题以来，已经知道了统一的成本距离坦Steiner树问题的常数因子近似算法。最近，Khazraei将近似因子从2.87提高到2.39并保持。我们进一步完善了他们的方法，并将近似因子降低到2.15。
In this paper, we consider the Uniform Cost-Distance Steiner Tree Problem in metric spaces, a generalization of the well-known Steiner tree problem. Cost-distance Steiner trees minimize the sum of the total length and the weighted path lengths from a dedicated root to the other terminals, which have a weight to penalize the path length. They are applied when the tree is intended for signal transmission, e.g. in chip design or telecommunication networks, and the signal speed through the tree has to be considered besides the total length. Constant factor approximation algorithms for the uniform cost-distance Steiner tree problem have been known since the first mentioning of the problem by Meyerson, Munagala, and Plotkin. Recently, the approximation factor was improved from 2.87 to 2.39 by Khazraei and Held. We refine their approach further and reduce the approximation factor down to 2.15.
