A note on the p - center problem

Authors

  • Rad Nader Jafari Department of Mathematics, Shahrood University of Technology, Shahrood, Iran

DOI:

https://doi.org/10.2298/YJOR1102199J

Keywords:

location theory, p - center problem

Abstract

The p - center problem is to locate p facilities in a network so as to minimize the longest distance between a demand point and its nearest facility. In this paper, we give a construction on a graph G which produces an infinite ascending chain G=G0≤G1≤G2≤... of graphs containing G such that given any optimal solution X for the p - center problem on G, X is an optimal solution for the p - center problem on i G for any i ≥ 1.

References

Bespamyatnikh, S., Bhattacharya, B., Keil, M., Kirkpatrick, D., and Segal, M., “Efficient algorithms for centers and medians in interval and circular-arc graphs”, Networks, 39 (2002) 144-152.

Drezner, Z., and Hamacher, H., Facility Location: Applications and Theory, Springer-Verlag, Berlin, 2002.

Frederickson, G., “Parametric search and locating supply centers in trees”, Proceedings of Workshop on Algorithms and Data Structures, (1991) 299-319.

Goldman, A.J., “Optimal center location in simple networks”, Transportation Science, 5 (1971) 212–221.

Hassin, R., and Tamir, A., “Improved complexity bounds for location problems on the real line”, Operation Research Letters, 10 (1991) 395–402.

Hua, L.K., et al. “Applications of mathematical methods to wheat harvesting”, Chinese Mathematics, 2 (1962) 77–91.

Kariv, O., and Hakimi, S.L., “An algorithmic approach to network location problems. Part I: the p-centers”, SIAM Journal on Applied Mathematics, 37 (1979) 513-538.

Kariv, O., and Hakimi, S.L., “An algorithmic approach to network location problems. Part II: p-medians”, SIAM Journal on Applied Mathematics, 37 (1979) 539–560.

Lan, Y.F., Wang, Y.L., and Suzuki, H., “A linear-time algorithm for solving the center problem on weighted cactus graphs”, Information Processing Letters, 71 (1999) 205-212.

Mirchandani, P.B., and Francis, R., Discrete Location Theory, J.Wiley, 1990.

Tamir, A., “Improved complexity bounds for center location problems on networks by using dynamic data structures”, SIAM Journal of Discrete Mathematics, 1 (1988) 377-396.

West, D.B., Introduction to Graph Theory, 2nd edition, Prentice Hall, USA, 2001.

Downloads

Published

2011-09-01

Issue

Vol. 21 No. 2 (2011)

Section

Research Articles

License

Copyright (c) 2011 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.