Facility location and the geometric minimum-diameter spanning tree. (Q1421033)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Facility location and the geometric minimum-diameter spanning tree. |
scientific article |
Statements
Facility location and the geometric minimum-diameter spanning tree. (English)
0 references
23 January 2004
0 references
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.
0 references
computational geometry
0 references
facility location
0 references
data structure
0 references
algorithm
0 references
discrete minimum-sum-two-center problem
0 references
minimum-diameter spanning tree
0 references
0 references