Various worst-case ratios of minimum weight bounded-degree spanning
trees for different degree bounds are still open, in particular
comparing τk to the weight τ of a minimum spanning tree.
τ4/τ≤1.035... for Euclidean distances in the plane,
τ4/τ≤1.25 for Manhattan distances in the plane,
and give matching lower bounds.
[KRY96] show that for Euclidean distances,
τ3/τ≤1.5 in the plane,
τ3/τ≤1.66... in arbitrary dimensions.
The first two of these bounds were improved to
Now settled by NP-hard proof in [FH09].