Approximating k-hop minimum spanning trees in Euclidean metrics

In the minimum-cost k-hop spanning tree (k-hop MST) problem, we are given a set S of n points in a metric space, a positive small integer k and a root point r∈S. We are interested in computing a rooted spanning tree of minimum cost such that the longest root-leaf path in the tree has at most k edges. We present a polynomial-time approximation scheme for the plane. Our algorithm is based on Arora's et al. [S. Arora, P. Raghavan, S. Rao, Approximation schemes for Euclidean k-medians and related problems, in: STOC'98: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, ACM Press, New York, NY, USA, 1998, pp. 106–113] techniques for the Euclidean k-median problem.