Optimal algorithms for the α-neighbor p-center problem

Assigning multiple service facilities to demand points is important when demand points are required to withstand service facility failures. Such failures may result from a multitude of causes, ranging from technical difficulties to natural disasters. The α-neighbor p-center problem deals with locating p service facilities. Each demand point is assigned to its nearest α service facilities, thus it is able to withstand up to α − 1 service facility failures. The objective is to minimize the maximum distance between a demand point and its αth nearest service facility. We present two optimal algorithms for both the continuous and discrete α-neighbor p-center problem. We present experimental results comparing the performance of the two optimal algorithms for α = 2. We also present experimental results showing the performance of the relaxation algorithm for α = 1, 2, 3.

► We present two optimal algorithms for the α-neighbor p-center problem. ► No optimal algorithm has previously been suggested for this problem. ► We compare the performance of the two new algorithms for α = 2. ► We experimentally show that the relaxation algorithm is more efficient. ► As the number of demand points increases, the advantage of relaxation increases.