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 ε > 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.