@inbook{f322a0a3d4ab4a9aab18cc901733589c,
title = "Approximation schemes for degree-restricted MST and Red-Blue Separation Problem",
abstract = "We develop a quasi-polynomial time approximation scheme for the Euclidean version of the Degree-restricted MST by adapting techniques used previously for approximating TSP. Given n points in the plane, d = 2 or 3, 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.",
author = "Sanjeev Arora and Chang, {Kevin L.}",
year = "2003",
doi = "10.1007/3-540-45061-0_16",
language = "English (US)",
isbn = "3540404937",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "176--188",
editor = "Baeten, {Jos C. M.} and Lenstra, {Jan Karel} and Joachim Parrow and Woeginger, {Gerhard J.}",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}