Abstract
We give a polynomial time approximation scheme (PTAS) for the rectilinear Steiner arborescence problem in the plane. The result is obtained by modifying Arora's PTAS for Euclidean TSP. The previously best known result was a 2-approximation algorithm.
| Original language | English |
|---|---|
| Pages | 1-7 |
| Number of pages | 7 |
| Publication status | Published - 2000 |
Keywords
- Analysis of algorithms
- suboptimal algorithms
- routing in VLSI design
- Networks/graphs
- tree algorithms
- rectilinear Steiner arborescence problem