论文标题
提高了两个欧几里得最大生成树问题的近似值
Improved approximation ratios for two Euclidean maximum spanning tree problems
论文作者
论文摘要
我们研究了与欧几里得平面中跨越树木有关的两个最大化问题。这些问题是否不知道NP-尚不清楚。我们提出两个问题的近似算法，具有更好的近似值。改进的比率主要是通过使用施泰纳比率来获得的，施泰纳比率尚未在此背景下使用。 （i）最长的非交叉跨越树：给定一组平面的点，目标是找到最大长度的非交叉跨越树。 Alon，Rajagopalan和Suri（SoCG 1993）首次研究了这个问题，并给出了0.5美元的AppRximation算法。多年来，由于Cabello等人，由于Cabello等人，近似值已连续提高到0.502美元，$ 0.503 $和0.512美元，这是当前最佳比率。改进是通过一系列想法，以前的作品和一些新想法（包括使用施泰纳比率）以及更精致的分析来实现的。 （ii）最长的跨越社区的树：给定平面中的区域（邻域）的集合，目标是在每个邻域中选择一个点，以使所选点上最长的跨越树具有最大的长度。我们为此问题提供了一种近似值$ 0.524 $的算法。以前由于陈和杜米特里库克（Dumitrescu）的最佳比率为0.511美元，而这又是第一个超过琐事比率$ 0.5 $的提高。我们的算法非常简单，其分析相对较短，并且在计算直径对点后需要线性时间。简单性来自我们的解决方案属于包含三颗恒星和一名双星的集合的事实。短暂性和改善来自用施纳比率的使用。
We study the following two maximization problems related to spanning trees in the Euclidean plane. It is not known whether or not these problems are NP-hard. We present approximation algorithms with better approximation ratios for both problems. The improved ratios are obtained mainly by employing the Steiner ratio, which has not been used in this context earlier. (i) Longest noncrossing spanning tree: Given a set of points in the plane, the goal is to find a maximum-length noncrossing spanning tree. Alon, Rajagopalan, and Suri (SoCG 1993) studied this problem for the first time and gave a $0.5$-approximation algorithm. Over the years, the approximation ratio has been successively improved to $0.502$, $0.503$, and to $0.512$ which is the current best ratio, due to Cabello et al.. We revisit this problem and improve the ratio further to $0.519$. The improvement is achieved by a collection of ideas, some from previous works and some new ideas (including the use of the Steiner ratio), along with a more refined analysis. (ii) Longest spanning tree with neighborhoods: Given a collection of regions (neighborhoods) in the plane, the goal is to select a point in each neighborhood so that the longest spanning tree on selected points has maximum length. We present an algorithm with approximation ratio $0.524$ for this problem. The previous best ratio, due to Chen and Dumitrescu, is $0.511$ which is in turn the first improvement beyond the trivial ratio $0.5$. Our algorithm is fairly simple, its analysis is relatively short, and it takes linear time after computing a diametral pair of points. The simplicity comes from the fact that our solution belongs to a set containing three stars and one double-star. The shortness and the improvement come from the use of the Steiner ratio.
