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