THE MODIFIED ONE-CENTER PROBLEM IN TREES: VARIATIONS AND APPLICATIONS
DOI:
https://doi.org/10.56238/revgeov17n5-143Keywords:
Location Problems, 1-Center Problem, Minmax ProblemsAbstract
An asymmetric variation of the 1-center problem in trees and a method for its solution in O(n) time are presented. The method employs a linear-time reduction of the problem, based on a technique using simulated vertices. Based on the computational results obtained, the presented method showed better performance compared to classical methods for solving the 1-center problem in trees.
Downloads
References
Burkard, R.; Krarup, J. A linear algorithm for the pos/neg-weighted 1-median problem on a cactus. Computing 60(3), 193–216. 1998.
Çalık, H.; Labbé, M.; Yaman, H. p-center problems. Location Science, 79–92. 2015.
Daskin, M.S.; Maass, K.L. “The p-Median Problem”. In: Laporte, G., Nickel, S., Saldanha da Gama, F. (eds.) Location Science, pp. 21–45. Springer. 2015.
Dearing, P.M.; Francis, R.L. A minimax location problem on a network. Transportation Science 8(4), 333–343. 1974.
Goldman, A.J. Optimal center location in simple networks. Transportation Science 5(2), 212–221. 1971.
Gortz, I.L.; Wirth, A. Asymmetry in k-center variants. Theoretical Computer Science 361(2), 188–199. 2006.
Hakimi, S.L. Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research 12(3), 450–459. 1964.
Hakimi, S.L. Optimum distribution of switching centers in a communication network and some related graph-theoretic problems. Operations Research 13(3), 462–475. 1965.
Hakimi, S.L.; Schmeichel, E.F.; Pierce, J.G. On p-centers in networks. Transportation Science 12(1), 1–15. 1978.
Hua, L.-K. et al. Application of mathematical methods to wheat harvesting. Chinese Mathematics 2(7791), 8. 1962.
Kariv, O.; Hakimi, S.L. An algorithmic approach to network location problems. I: The p-centers. SIAM Journal on Applied Mathematics 37(3), 513–538. 1979.
Kariv, O.; Hakimi, S.L. An algorithmic approach to network location problems. II: The p-medians. SIAM Journal on Applied Mathematics 37(3), 539–560. 1979.
Liu, Y. An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones. Computers & Operations Research 111(1), 1–20. 2019.
Megiddo, N. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput. 12(4), 759–776. 1983.
Nguyen, K.T.; Nguyen-Thu, H.; Hung, N.T. Combinatorial algorithms for the uniformcost inverse 1-center problem on weighted trees. Acta Math. Vietnam 44(3), 813–831. 2019.
Tamir, A. An O(pn2) algorithm for the p-median and related problems on tree graphs. Operations Research Letters 19(2), 59–64. 1996.
Tansel, B.; Francis, R.L.; Lowe, T.J. Location on networks: A survey. Part I: The p-center and p-median problems. Management Science 29(2), 482–497. 1983.
Wang, H.; Zhang, J. An O(n log n)-time algorithm for the k-center problem in trees. SIAM J. Comput. 50(2), 602–635. 2021.
