On the bounded-hop MST problem on random Euclidean instances

The d-Dimh-hops MST problem is defined as follows: given a set S of points in the d-dimensional Euclidean space and s∈S, find a minimum-cost spanning tree for S rooted at s with height at most h. We investigate the problem for any constant h and d>0. We prove the first nontrivial lower bound on the solution cost for almost all Euclidean instances (i.e. the lower bound holds with high probability). Then we introduce an easy-to-implement, fast divide et impera heuristic and we prove that its solution cost matches the lower bound.