A Multifacility Location Problem on Median Spaces
A Multifacility Location Problem on Median Spaces
复制标题
中位空间上的多设施选址问题
DOI：
10.1016/0166-218x(95)00115-8
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
V. Chepoi
中科院分区：
文献类型：
--
作者：
V. Chepoi
本文研究了在已有k个设施点的情况下，如何在中间空间中安置n个新设施点的问题。目标是最小化距离的加权和。建立了充分必要条件。在此基础上提出了一种多项式算法。该算法需要解决一系列的最小切割问题。对于中值图和网络以及具有<$V <$点的有限中值空间，该算法的复杂性为O（<$V <$3 +<$V <$$>（n）），其中<$（n）是所应用的最大流算法的复杂性.对于一个简单的直线多边形P，它有N条边，并具有直线距离，其类似算法需要O（N + k（logN + logk + n（n）时间，对于顶点限制的多设施选址问题，其类似算法需要O（N + k n（n））时间。
This paper is concerned with the problem of locating n new facilities in the median space when there are k facilities already located. The objective is to minimize the weighted sum of distances. Necessary and sufficient conditions are established. Based on these results a polynomial algorithm is presented. The algorithm requires the solution of a sequence of minimum-cut problems. The complexity of this algorithm for median graphs and networks and for finite median spaces with ¦V¦points is O (¦V¦3+ ¦V¦ψ(n)) , where ψ(n) is the complexity of the applied maximum-flow algorithm. For a simple rectilinear polygon P with N edges and equipped with the rectilinear distance the analogical algorithm requires O(N + k(logN + logk + ψ(n))) time and O(N + kψ(n)) time in the case of the vertex-restricted multifacility location problem.