A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane
A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane
复制标题
平面上几何k-MST问题的常因子逼近算法
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
S. Vempala
中科院分区：
文献类型：
--
作者：
Joseph S. B. Mitchell;Avrim Blum;P. Chalasani;S. Vempala
我们证明了平面上的任意直线多边形细分都可以转化为长度至多是原细分长度两倍的“断头式”细分。“断头台”细分有一个简单的递归结构，允许人们使用动态规划在多项式时间内搜索“最佳”这样的细分。特别地，我们的主要定理的一个结果是一个非常简单的证明，证明了平面上的k-MST问题有一个常数因子多项式时间近似算法：对于L1度量，我们得到了因子2(分别为3)，对于L2(欧几里得)度量，在允许(分别为，不允许)Steiner点的情况下，得到了$2Sqrt{2}$(分别为3.266)。
We show that any rectilinear polygonal subdivision in the plane can be converted into a "guillotine" subdivision whose length is at most twice that of the original subdivision. "Guillotine" subdivisions have a simple recursive structure that allows one to search for "optimal" such subdivisions in polynomial time, using dynamic programming. In particular, a consequence of our main theorem is a very simple proof that the k-MST problem in the plane has a constant-factor polynomial-time approximation algorithm: we obtain a factor of 2 (resp., 3) for the L1 metric, and a factor of $2sqrt{2}$ (resp., 3.266) for the L2 (Euclidean) metric in the case in which Steiner points are allowed (resp., not allowed).