Approximation schemes for degree-restricted MST and red-blue separation problems

摘要

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 epsilon > 0, the scheme finds an approximation with cost within 1 + epsilon 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 epsilon > 0, the scheme finds an approximation with cost within 1 + epsilon of the cost of the optimum separating polygon of the input nodes, in nearly linear time.