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.
|Original language||English (US)|
|Number of pages||13|
|Journal||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|State||Published - Dec 1 2003|
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)