A simple heuristic for the p-centre problem. (English) Zbl 0556.90019

We describe a simple heuristic for determining the p-centre of a finite set of weighted points in an arbitrary metric space. The computational effort is O(np) for an n-point set. We show that the ratio of the objective function value of the heuristic solution to that of the optimum is bounded by \(\min (3,1+\alpha)\), where \(\alpha\) is the maximum weight divided by the minimum weight of points in the set.


90B05 Inventory, storage, reservoirs
65K05 Numerical mathematical programming methods
Full Text: DOI


[1] Drezner, Z, The p-centre problem — heuristic and optimal algorithms, J. oper. res. soc., 35, 741-748, (1984) · Zbl 0544.90024
[2] Dyer, M.E, On a multidimensional search technique and its application to the Euclidean one-centre problem, (1984), Mathematics Department, Teesside Polytechnic · Zbl 0613.68044
[3] Fowler, R.J; Paterson, M.S; Tanimoto, S.L, Optimal packing and covering in the plane are NP-complete, (), 133-137 · Zbl 0469.68053
[4] Hochbaum, D.S; Shmoys, D.B, A best possible heuristic for the k-centre problem, (1983), University of California Berkeley
[5] Hochbaum, D.S; Shmoys, D.B, Powers of graphs: A powerful approximation technique for bottleneck problems, ()
[6] Hsu, W.L; Nemhauser, G.L, Easy and hard bottleneck location problems, Discrete appl. math., 1, 209-216, (1979) · Zbl 0424.90049
[7] Kariv, O; Hakimi, S.L, An algorithm approach to network location problems I: the p-centers, SIAM J. appl. math., 37, 513-538, (1979) · Zbl 0432.90074
[8] Masuyama, S; Ibaraki, T; Hasegawa, T, The computational complexity of the m-centre problems on the plane, Transactions of the IECE of Japan, E64, 57-64, (1981)
[9] Megiddo, N; Supowit, K.J, On the complexity of some common geometric location problems, SIAM J. computing, 18, 182-196, (1984) · Zbl 0534.68032
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.