## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 189-210 |

Number of pages | 22 |

Journal | Algorithmica (New York) |

Volume | 40 |

Issue number | 3 |

DOIs | |

State | Published - Aug 2004 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- Computer Science Applications
- Applied Mathematics

## Keywords

- Approximation algorithm
- Degree-Restricted Minimum Spanning Tree
- Low degree