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

Dyer, M. E.; Frieze, A. M.

Oper. Res. Lett. 3, 285-288 (1985).

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.

MSC:

90B05	Inventory, storage, reservoirs
65K05	Numerical mathematical programming methods

Keywords:

heuristic; p-centre; finite set of weighted points

References:

[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