论文标题
找到几乎紧密的见证树
Finding Almost Tight Witness Trees
论文作者
论文摘要
本文解决了一个称为证人树问题的图表优化问题，该问题寻求图形的一生，最小化某些非线性目标函数。这个问题引起了人们的关注，因为它在分析两个基本网络设计问题的最佳近似算法中起着至关重要的作用：Steiner Tree和Node-Tree增强。我们将展示明智的见证树选择如何改善节点树的近似值，并在特殊的图表中为Steiner树提供了改进的近似值。
This paper addresses a graph optimization problem, called the Witness Tree problem, which seeks a spanning tree of a graph minimizing a certain non-linear objective function. This problem is of interest because it plays a crucial role in the analysis of the best approximation algorithms for two fundamental network design problems: Steiner Tree and Node-Tree Augmentation. We will show how a wiser choice of witness trees leads to an improved approximation for Node-Tree Augmentation, and for Steiner Tree in special classes of graphs.
