zbMATH — the first resource for mathematics

The \(p\)-neighbor \(k\)-center problem. (English) Zbl 1338.68290
Summary: The \(k\)-center problem with triangle inequality is that of placing \(k\) center nodes in a weighted undirected graph in which the edge weights obey the triangle inequality, so that the maximum distance of any node to its nearest center is minimized. In this paper, we consider a generalization of this problem where, given a number \(p\), we wish to place \(k\) centers so as to minimize the maximum distance of any non-center node to its pth closest center. We derive a best possible approximation algorithm for this problem.

68W25 Approximation algorithms
90B80 Discrete location and assignment
Full Text: DOI Link
[1] Feder, T.; Greene, D.H., Optimal algorithms for approximate clusters, (), 434-444
[2] González, T.F., Clustering to minimize the maximum intercluster distance, Theoret. comput. sci., 38, 293-306, (1985) · Zbl 0567.62048
[3] Handler, G.Y.; Mirchandani, P.B., Location on networks: theory and algorithms, (1979), MIT Press Cambridge, MA · Zbl 0533.90026
[4] Hochbaum, D.S.; Shmoys, D.B., A best possible heuristic for the k-center problem, Math. oper. res., 10, 180-184, (1985) · Zbl 0565.90015
[5] Hochbaum, D.S.; Shmoys, D.B., A unified approach to approximation algorithms for bottleneck problems, J. ACM, 33, 533-550, (1986)
[6] Kariv, O.; Hakimi, S.L., An algorithmic approach to network location problems. part I: the p-centers problem, SIAM J. appl. math., 37, 513-538, (1979) · Zbl 0432.90074
[7] Khuller, S.; Pless, R.; Sussmann, Y., Fault-tolerant K-center problems, (), (to appear) · Zbl 0944.68141
[8] Also appears as Tech. Rept. UMIACS-TR-96-40.
[9] Krumke, S.O., On a generalization of the p-center problem, Inform. process. lett., 56, 67-71, (1995)
[10] Plesnik, J., A heuristic for the p-center problem in graphs, Discrete appl. math., 17, 263-268, (1987) · Zbl 0637.05020
[11] Ravi, S.S.; Rosenkrantz, D.J.; Tayi, G.K., Facility dispersion problems: heuristics and special cases, (), 355-366 · Zbl 0765.68055
[12] Wang, Q.; Cheng, K.H., A heuristic algorithm for in: the k-center problem with vertex weight, (), 388-396
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.