View Related Documents

Abstract

Let tauK 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 tau2 = 2 and tau5 = 1. In STOC lsquo94, Khuller, Raghavachari, and Young established the following inequalities: 1.103 < tau3 \le 1.5 and 1.035 < tau4 \le 1.25. We present the first improved upper bounds: tau3 < 1.402 and tau4 < 1.143. As a result, we obtain better approximation algorithms for Euclidean minimum bounded-degree spanning trees. Let tauK (d) be the analogous ratio in d-dimensional space. Khuller et al. showed thattau3 (d) < 1.667 for any d. We observe that tau3 (d) < 1.633.

Fulltext Preview

Image of the first page of the fulltext document