Euclidean bounded-degree spanning tree ratios
Timothy M. Chan · 2003
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 < 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