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 \le 1.5 and 1.035 <
4 \le 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.