TY - GEN

T1 - Facility location and the geometric minimum-diameter spanning tree

AU - Gudmundsson, J.

AU - Haverkort, H.J.

AU - Park, S.M.

AU - Shin, C.S.

AU - Wolff, A.

PY - 2002

Y1 - 2002

N2 - 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 Euclidian length of the longest path.It is known that there is always a mono-or a dipolar MDST, i.e.a MDST with one or two nodes of degree greater 1, respectively. The more difficult dipolar case can so far only be solved i slightly subcubic time.
This paper has two aims. First,we present a solution to a new data structure for facility location, 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)to the closer center. This is of interest if the two centers do not only serve their customers (as in the case of the 2CP),but frequently have to exchange goods or personnel between themselves.We show that this problem can be solved in O (n 2 log n)time and that it yields a factor-4/3 approximation of the MDST.
Second, we give two fast approximation schemes for the MDST.One uses a grid and takes O*(E6-1/3+n) time, where E =1 /¿ and the O*-notation hides terms of type O (log O(1) E).The other uses the well- separated pair decomposition and takes O (nE 3+En log n)time. A combination of the two approaches runs in O*(E 5+n) time. Both schemes can also be applied to MSST and 2CP.

AB - 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 Euclidian length of the longest path.It is known that there is always a mono-or a dipolar MDST, i.e.a MDST with one or two nodes of degree greater 1, respectively. The more difficult dipolar case can so far only be solved i slightly subcubic time.
This paper has two aims. First,we present a solution to a new data structure for facility location, 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)to the closer center. This is of interest if the two centers do not only serve their customers (as in the case of the 2CP),but frequently have to exchange goods or personnel between themselves.We show that this problem can be solved in O (n 2 log n)time and that it yields a factor-4/3 approximation of the MDST.
Second, we give two fast approximation schemes for the MDST.One uses a grid and takes O*(E6-1/3+n) time, where E =1 /¿ and the O*-notation hides terms of type O (log O(1) E).The other uses the well- separated pair decomposition and takes O (nE 3+En log n)time. A combination of the two approaches runs in O*(E 5+n) time. Both schemes can also be applied to MSST and 2CP.

U2 - 10.1007/3-540-45753-4_14

DO - 10.1007/3-540-45753-4_14

M3 - Conference contribution

SN - 3-540-44186-7

T3 - Lecture Notes in Computer Science

SP - 146

EP - 160

BT - Approximation algorithms for combinatorial optimization : proceedings APPROX 2002, Rome Italy, september 17-21, 2002

A2 - Jansen, K.

A2 - Leonardi, S.

A2 - Vazirani, V.

PB - Springer

CY - Berlin

ER -