Optimal algorithms for the \(\alpha\)-neighbor \(p\)-center problem.

*(English)*Zbl 1292.90159Summary: 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 \(\alpha\)-neighbor \(p\)-center problem deals with locating \(p\) service facilities. Each demand point is assigned to its nearest \(\alpha\) service facilities, thus it is able to withstand up to \(\alpha-1\) service facility failures. The objective is to minimize the maximum distance between a demand point and its \(\alpha\)th nearest service facility. We present two optimal algorithms for both the continuous and discrete \(\alpha\)-neighbor \(p\)-center problem. We present experimental results comparing the performance of the two optimal algorithms for \(\alpha=2\). We also present experimental results showing the performance of the relaxation algorithm for \(\alpha=1, 2, 3\).

##### MSC:

90B80 | Discrete location and assignment |

90C60 | Abstract computational complexity for mathematical programming problems |