Grade of Service Steiner Minimum Trees in the Euclidean Plane
Grade of Service Steiner Minimum Trees in the Euclidean Plane
复制标题
欧几里德平面上的服务等级斯坦纳最小树
DOI：
10.1007/s00453-001-0050-6
复制
发表时间：
2001
期刊：
影响因子：
1.1
通讯作者：
D. Du
中科院分区：
文献类型：
--
作者：
G. Xue;Guohui Lin;D. Du
Abstract.设P = {p1，p2，\ldots，pn }是欧几里得平面上的n个端点的集合，其中点pi有等级为g（pi）∈ {1，2，\ldots，n}的服务请求.设0 < c（1）< c（2）<s < c（n）是n个真实的数.服务等级Steiner最小树（GOSST）问题要求连接点集P和一些服务等级为0的Steiner点的最小费用网络，使得（1）在每对端点pi和pj之间存在一条最小服务等级至少为\min（g（pi），g（pj））的路径;以及（2）在满足（1）的所有互连网络中，网络的成本最小，其中具有等级g服务的边的成本是边的欧几里德长度与c（g）的乘积。GOSST问题是欧氏Steiner最小树问题的推广，其中所有终端点具有相同的服务等级请求。当终端点只对两个（分别为三个）不同等级的服务请求时，我们给出了一个性能比为4 3 ρ（分别为（5+ 4 2）/7）ρ）的多项式时间近似算法，其中ρ是Euclidean Steiner最小树问题的近似算法所达到的性能比.在一般情况下，我们证明了存在一个GOSST，它是一个完整的Steiner拓扑或其退化下的最小费用网络。给出了一个强有力的邻域点算法，在O（n1.5（logn + log（1/ε）时间内求出给定拓扑下最小费用网络的（1+ε）-逼近及其退化.我们还证明了一个下界定理，使有效的修剪在分支定界方法，部分列举了完整的施泰纳拓扑搜索的GOSST。然后，我们提出了一个k -最优的启发式算法来计算好的解决方案时，问题的大小是太大的分支定界算法。给出了初步的计算结果。
AbstractAbstract. Let P = {p1, p2, \ldots, pn } be a set of n {\lilsf terminal points} in the Euclidean plane, where point pi has a {\lilsf service request of grade} g(pi) ∈ {1, 2, \ldots, n} . Let 0 < c(1) < c(2) < ⋅s < c(n) be n real numbers. The {\lilsf Grade of Service Steiner Minimum Tree (GOSST)} problem asks for a minimum cost network interconnecting point set P and some {\lilsf Steiner points} with a service request of grade 0 such that (1) between each pair of terminal points pi and pj there is a path whose minimum grade of service is at least as large as \min(g(pi), g(pj)) ; and (2) the cost of the network is minimum among all interconnecting networks satisfying (1), where the cost of an edge with service of grade g is the product of the Euclidean length of the edge with c(g) . The GOSST problem is a generalization of the Euclidean Steiner minimum tree problem where all terminal points have the same grade of service request. When there are only two (three, respectively) different grades of service request by the terminal points, we present a polynomial time approximation algorithm with performance ratio \frac 4 3 ρ (((5+4\sqrt 2 )/7)ρ , respectively), where ρ is the performance ratio achieved by an approximation algorithm for the Euclidean Steiner minimum tree problem. For the general case, we prove that there exists a GOSST that is the minimum cost network under a full Steiner topology or its degeneracies. A powerful interior-point algorithm is used to find a (1+ε) -approximation to the minimum cost network under a given topology or its degeneracies in O(n1.5(log n + log (1/ε))) time. We also prove a lower bound theorem which enables effective pruning in a branch-and-bound method that partially enumerates the full Steiner topologies in search for a GOSST. We then present a k -optimal heuristic algorithm to compute good solutions when the problem size is too large for the branch-and-bound algorithm. Preliminary computational results are presented.