Approximation Schemes for Degree-Restricted MST and Red–Blue Separation Problems
Approximation Schemes for Degree-Restricted MST
and Red–Blue Separation Problems
复制标题
度限制 MST 的近似方案
作者：
Sanjeev Arora;Kevin L. Chang
抽象的
我们为欧几里德版本的拟多项式时间近似方案
通过采用 Arora 之前用于近似 TSP 的技术来解决度限制 MST 问题。
给定平面上的 n 个点，d = 3 或 4，并且 ε > 0，该方案找到成本在 1 + ε 范围内的近似值
具有所有节点的度数至多为 d 的属性的最低成本生成树。
我们还为红蓝的欧几里得版本开发了多项式时间近似方案
分离问题，再次扩展了阿罗拉的技术。给定 ε > 0，该方案找到一个近似值
成本在输入节点的最佳分离多边形的成本的 1+ ε 范围内，几乎是线性时间。
Abstract
We develop a quasi-polynomial time approximation scheme for the Euclidean version of the
Degree-Restricted MST Problem by adapting techniques used previously by Arora for approximating TSP.
Given n points in the plane, d = 3 or 4, and ε > 0, the scheme finds an approximation with cost within 1 + ε
of the lowest cost spanning tree with the property that all nodes have degree at most d.
We also develop a polynomial time approximation scheme for the Euclidean version of the Red–Blue
Separation Problem, again extending Arora’s techniques. Given ε > 0, the scheme finds an approximation
with cost within 1+ ε of the cost of the optimum separating polygon of the input nodes, in nearly linear time.