The continuous p-median of a network. (English) Zbl 0675.90026

Summary: The distance between an edge and a point of a network N is defined as the maximum distance from that point to any point on that edge. A continuous median of N is a point of N such that the sum of the distances between all edges and that point is minimum. A continuous p-median is a set of p points of N such that the sum for all edges of the distance to the closest point of that set is minimum. It is shown that the set of vertices and middle points of edges always contains a continuous p- median. Therefore, powerful algorithms for the usual p-median problem can be brought to bear. Moreover, algorithms requiring \(O(m^ 2)\) operations in worst case for determining the set of all continuous and conditional continuous medians of N are obtained. A linear algorithm for the set of all continuous medians of a tree is also provided.


90B05 Inventory, storage, reservoirs
90C35 Programming involving graphs or networks
Full Text: DOI


[1] Beasley, Eur J. Oper. Res. 21 pp 270– (1985)
[2] Chen, Networks 12 pp 335– (1982)
[3] Christofides, Eur. J. Oper. Res. 10 pp 196– (1982)
[4] Dijkstra, Numer. Math. 1 pp 269– (1959)
[5] Erlenkotter, Oper. Res. 26 pp 992– (1978)
[6] Frank, Oper. Res. 15 pp 409– (1967)
[7] Goldman, Transp. Sci. 5 pp 212– (1971)
[8] and , Graphes et algorithmes. Eyrolles, France (1979).
[9] Hakimi, Oper. Res. 13 pp 462– (1965)
[10] Hakimi, Oper. Res. 12 pp 967– (1972)
[11] and , Location on Networks, M.I.T. Press, Cambridge, MA (1979).
[12] , and , The continuous center set of a network. Submitted for publication (1988).
[13] Krarup, Region. Sci. and Urb. Econ. 12 pp 547– (1982)
[14] Levy, Oper. Res. Quart. 18 pp 433– (1972)
[15] Minieka, Oper. Res. 25 pp 641– (1977)
[16] Minieka, Networks 10 pp 265– (1980)
[17] Wendell, Transp. Sci. 7 pp 18– (1973)
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.