A note on the m-center problem with rectilinear distances. (English) Zbl 0699.90028

Summary: Given n demand points on a plane, the problem we consider is to locate a given number, m, of facilities on the plane so that the maximum of the set of rectilinear distances of each demand point to its nearest facility is minimized. This problem is known as the m-center problem on the plane. A related problem seeks to determine, for a given r, the minimum number of facilities and their locations so as to ensure that every point is within r units of rectilinear distance from its nearest facility. We formulate the latter problem as a problem of covering nodes by cliques of an intersection graph. Certain bounds are established on the size of the problem. An efficient algorithm is provided to generate this set-covering problem. Computational results with this approach are summarized.


90B05 Inventory, storage, reservoirs
90C35 Programming involving graphs or networks
90C10 Integer programming
Full Text: DOI


[1] Dearing, P.M., On some minimax location problems using rectilinear distances, (1972), University of Florida Gainesville, FL, unpublished Ph.D. dissertation
[2] Dearing, P.M., Location problems, Operations research letters, 4/3, 95-98, (1985) · Zbl 0572.90022
[3] Drezner, Z., The p-center problem—heuristic and optimal algorithms, Journal of the operational research society, 35, 741-748, (1984) · Zbl 0544.90024
[4] Elzinga, J.; Hearn, D.W., Geometrical solutions for some minimax location problems, Transportation science, 6/4, 379-394, (1971)
[5] Francis, R.L., A geometrical solution procedure for a rectilinear distance minimax location problem, AIIE transactions, 4/4, 328-332, (1971)
[6] Francis, R.L., Some aspects of a minimax location problem, Operations research, 15, 1163-1168, (1967)
[7] Garfinkel, R.S.; Nemhauser, G.L., Integer programming, (1972), Wiley New York · Zbl 0271.90028
[8] Garfinkel, R.S.; Noebe, A.W.; Rao, M.R., The m-center problem: minimax facility location, Management science, 23/10, 1133-1142, (1977) · Zbl 0369.90125
[9] Handler, G.Y., Minimax location of a facility in an undirected tree graph, Transportation science, 7, 287-293, (1973)
[10] Masuyama, S.; Ibaraki, T.; Hasegawa, T., The computational complexity of the m-center problems on the plane, Transactions of the IECE of Japan, E64/2, 57-64, (1981)
[11] Minieka, E., The m-center problem, SIAM review, 12, 138-139, (1970) · Zbl 0193.24204
[12] Reingold, E.M.; Nievergelt, J.; Deo, N., Combinatorial algorithms, (1977), Prentice-Hall Englewood Cliffs, NJ · Zbl 0478.68058
[13] Roberts, F.S., Graph theory and its application to problems of society, () · Zbl 0193.24301
[14] Rockafellar, R.T., Convex analysis, (1969), Princeton University Press Princeton · Zbl 0186.23901
[15] Vijay, J., An algorithm for the p-center problem in the plane, Transportation science, 19, 235-245, (1985) · Zbl 0608.90020
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.