On the rectangular p-center problem. (English) Zbl 0614.90034

Drezner, Zvi

Nav. Res. Logist. 34, No. 1-2, 229-234 (1987).

The p-center problem consists in finding the location of p facilities such that any among n given points is as close as possible to anyone of these facilities. In other words minimize the maximal distance of the given points to their nearest facility.
This paper studies ways to solve the p-center problem in the plane, when distances are rectilinear. After describing the well-known O(n) solution method for the 1-center problem, it is shown how the 2-center problem may be solved in O(n) time, and the 3-center problem in O(n log n) time.
Making use of this last result an \(O(n^{2p-5}\log n)\) algorithm is suggested for cases where \(p>3\), which can further be simplified into an O(n log\({}^{p-2}n)\) heuristic.

Reviewer: F.Plastria

MSC:

90B05	Inventory, storage, reservoirs
68Q25	Analysis of algorithms and problem complexity

Keywords:

facility locating; minimax problem; rectilinear distance; p-center problem

References:

[1]	Chen, Naval Research Logistics Quarterly 30 pp 449– (1983)
[2]	and , ”Location and Layout Planning,” in Lecture Notes in Economics and Mathematical Systems No. 238, 134 pages, Springer-Verlag, Berlin, 1985. · Zbl 0554.90028
[3]	Drezner, Journal of the Operational Research Society 35 pp 741– (1984)
[4]	Drezner, Transportation Science 18 pp 351– (1984)
[5]	Drezner, SIAM Journal of Algebraic and Discrete Methods 1 pp 315– (1980)
[6]	Drezner, Computers and Operations Research 12 pp 603– (1985)
[7]	Elzinga, Transportation Science 6 pp 379– (1972)
[8]	and , Facility Layout and Location, Prentice-Hall, Englewood Cliffs, NJ, 1974.
[9]	Hearn, Operations Research 30 pp 777– (1982)
[10]	Kariv, SIAM Journal of Applied Mathematics 37 pp 513– (1979)
[11]	Ward, Operations Research 28 pp 836– (1980)