A heuristic for the p-center problem in graphs. (English) Zbl 0637.05020
The author gives an algorithm of \(O(n^ 2\log n)\) running time with a worst-case error ratio of 2 for the p-centerproblem in a connected graph of n nodes and m edges with edge lengths and vertex weights. A slight modification of the algorithm provides a ratio 2 also for the absolute p- center problem with running time \(O(mn^ 2\log n)\). Both heuristics are best possible.
Reviewer: H.T.Lau
References:
| [1] | Christofides, N., Graph Theory: an algorithmic Approach (1975), Academic Press: Academic Press London · Zbl 0321.94011 |
| [2] | Drezner, Z., The \(p\)-centre problem - heuristic and optimal algorithms, J. Oper. Res. Soc., 35, 741-748 (1984) · Zbl 0544.90024 |
| [3] | Dyer, M. E.; Frieze, A. M., A simple heuristic for the \(p\)-centre problem, Oper. Res. Lett., 3, 285-288 (1985) · Zbl 0556.90019 |
| [4] | Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L., Optimal packing and covering in the plane are NP-complete, Inform. Process. Lett., 12, 133-137 (1981) · Zbl 0469.68053 |
| [5] | Hakimi, S. L., Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Res., 12, 450-459 (1964) · Zbl 0123.00305 |
| [6] | Hakini, S. L., Optimal distribution of switching centers in a communications network and some related graph-theoretic problems, Operations Res., 13, 462-475 (1965) · Zbl 0135.20501 |
| [7] | 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 |
| [8] | D.S. Hochbaum and D.B. Shmoys, Powers of graphs: a powerful approximation algorithm technique for bottleneck problems, J. Assoc. Comput. Mach., to appear.; D.S. Hochbaum and D.B. Shmoys, Powers of graphs: a powerful approximation algorithm technique for bottleneck problems, J. Assoc. Comput. Mach., to appear. |
| [9] | Hsu, W. L.; Nemhauser, G. I., Easy and hard bottleneck location problems, Discrete Appl. Math., 1, 209-215 (1979) · Zbl 0424.90049 |
| [10] | Johnson, D. B., Efficient algorithms for Shortest paths in sparse networks, J. Assoc. Comput. Mach., 24, 1-13 (1977) · Zbl 0343.68028 |
| [11] | Kariv, O.; Hakimi, S. L., An algorithmic approach to network location problems I: the \(p\)-centers, SIAM J. Appl. Math., 37, 513-538 (1979) · Zbl 0432.90074 |
| [12] | Masuyama, S.; Ibaraki, T.; Hasegawa, T., The computational complexity of the \(m\)-centre problems on the plane, Trans. IECE Japan, E64, 57-64 (1981) |
| [13] | Megiddo, N.; Supowit, K. J., On the complexity of some common geometric location problems, SIAM J. Comput., 18, 182-196 (1984) · Zbl 0534.68032 |
| [14] | Minieka, E., The centers and medians of a graph, Operations Res., 25, 641-650 (1977) · Zbl 0383.90046 |
| [15] | Plesnik, J., On the computational complexity of centers locating in a graph, Aplikace Mat., 25, 445-452 (1980) · Zbl 0454.68026 |
| [16] | Tansel, B. C.; Francis, R. L.; Lowe, T. J., Location on networks: a survey; part I: the \(p\)-center and \(p\)-median problems, Management Sci., 29, 482-497 (1983) · Zbl 0513.90022 |
| [17] | Tansel, B. C.; Francis, R. L.; Lowe, T. J., Location on networks: a survey; part II: exploiting tree network structure, Management Sci., 29, 498-511 (1983) · Zbl 0513.90023 |
| [18] | Wong, R. T., Location and network design, (O’hEigeartaigh, M.; Lenstra, J. K.; Rinoony Kan, A. H.G., Combinatorial Optimization: Annotated Bibliographies (1985), Wiley: Wiley New York), 129-147 · Zbl 0556.90018 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
