Facility location and the geometric minimum-diameter spanning tree. (Q1421033)

One of the results of this interesting paper discusses a new facility location problem, the discrete minimum-sum-two-center problem. Let \(P\) be a set of \(n\) points in the plane. The geometric minimum-diameter spanning tree (MDST) of \(P\) is a tree that spans \(P\) and minimizes the Euclidean length of the longest path. It is known that there is always a mono- or a dipolar MDST. The authors present a solution to the minimum-sum dipolar spanning tree (MSST), that mediates between the minimum-diameter dipolar spanning tree and the discrete two-center problem (2CP) in the following sense: find two centers \(p\) and \(q\) in \(P\) that minimize the sum of their distance plus the distance of any other point (client) of the closer center. It is shown that there is an algorithm that computes the corresponding MSST in \(O(n^2 \log n)\) time and that a variant of this tree is a factor-\(\frac{4}{3}\)-approximation of the MDST. The following open problem is given: Is there a near quadratic-time algorithm for the MSST that uses \(O(m^2)\) space. On the other hand four approximation schemes for the MSST are presented. Open problems are discussed. Some of the methods given also work for higher-dimensional point sets.