Abstract
Let τk be the worst-case (supremum) ratio of the weight of the minimum degree-K spanning tree to the weight of the minimum spanning tree, over all finite point sets in the Euclidean plane. It is known that τ2 = 2 and τ5 = 1. In STOC'94, Khuller, Raghavachari, and Young established the following inequalities: 1.103 < τ3 ≤ 1.5 and 1.035 < τ4 ≤ 1.25. We present the first improved upper bounds: τ3 < 1.402 and τ4 < 1.143. As a result, we obtain better approximation algorithms for Euclidean minimum bounded-degree spanning trees. Let τk(d) be the analogous ratio in d-dimensional space. Khuller et al. showed that τ3(d) < 1.667 for any d. We observe that τ3(d) < 1.633.
Original language | English (US) |
---|---|
Pages | 11-19 |
Number of pages | 9 |
DOIs | |
State | Published - 2003 |
Externally published | Yes |
Event | Nineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States Duration: Jun 8 2003 → Jun 10 2003 |
Other
Other | Nineteenth Annual Symposium on Computational Geometry |
---|---|
Country/Territory | United States |
City | san Diego, CA |
Period | 6/8/03 → 6/10/03 |
Keywords
- Approximation
- Discrete geometry
- Minimum spanning trees
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics