Premium
The conditional p ‐center problem in the plane
Author(s) -
Chen R.,
Handler Y.
Publication year - 1993
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199302)40:1<117::aid-nav3220400108>3.0.co;2-0
Subject(s) - center (category theory) , plane (geometry) , mathematics , computer science , geometry , crystallography , chemistry
An algorithm is given for the conditional p ‐center problem, namely, the optimal location of one or more additional facilities in a region with given demand points and one or more preexisting facilities. The solution dealt with here involves the minimax criterion and Euclidean distances in two‐dimensional space. The method used is a generalization to the present conditional case of a relaxation method previously developed for the unconditional p ‐center problems. Interestingly, its worst‐case complexity is identical to that of the unconditional version, and in practice, the conditional algorithm is more efficient. Some test problems with up to 200 demand points have been solved. © 1993 John Wiley & Sons, Inc.