zbMATH — the first resource for mathematics

Optimal algorithms for the \(\alpha\)-neighbor \(p\)-center problem. (English) Zbl 1292.90159
Summary: 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\).

90B80 Discrete location and assignment
90C60 Abstract computational complexity for mathematical programming problems
PDF BibTeX Cite
Full Text: DOI