@inbook{a82a0d98073949a1b50387223cc011ed,

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 = "American English",

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",

}