Opuscula Math. 44, no. 1 (2024), 135-149
https://doi.org/10.7494/OpMath.2024.44.1.135
Opuscula Mathematica
The extensive 1-median problem with radius on networks
Tran Hoai Ngoc Nhan
Nguyen Thanh Hung
Kien Trung Nguyen
Abstract. The median location problem concerns finding locations of one or several new facilities that minimize the overall weighted distances from the existing to the new facilities. We address the problem of locating one new facility with a radius \(r\) on networks. Furthermore, the radius \(r\) is flexible and the objective function is the conic combination of the traditional 1-median function and the value \(r\). We call this problem an extensive 1-median problem with radius on networks. To solve the problem, we first induce the so-called finite dominating set, that contains all points on the underlying network and radius values which are candidate for the optimal solution of the problem. This helps to develop a combinatorial algorithm that solves the problem on a general network \(G=(V,E)\) in \(O(|E||V|^3)\) time. We also consider the underlying problem with improved algorithm on trees. Based the convexity of the objective function with variable radius, we develop a linear time algorithm to find an extensive 1-median with radius on the underlying tree.
Keywords: extensive facility, median problem, tree, convex.
Mathematics Subject Classification: 90B10, 90C35.
- A. Berger, A. Grigoriev, A. Winokurow, An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions, Comput. Optim. Appl. 68 (2017), 661-669.
- B. Bhattacharya, Q. Shi, A. Tamir, Optimal algorithms for the path/tree-shaped facility location problems in trees, Algorithmica 55 (2009), 601-618. https://doi.org/10.1007/s00453-007-9157-8
- R. Chandrasekaran, The weighted euclidean 1-center problem, Oper. Res. Lett. 1 (1982), 111-112. https://doi.org/10.1016/0167-6377(82)90009-8
- Z. Drezner, H.W. Hamacher, Facility Location - Applications and Theory, Springer-Verlag, Berlin, Heidelberg, 2002.
- H.A. Eiselt, V. Marianov, Foundations of Location Analysis, Springer, 2011.
- A.J. Goldman, Optimal center location in simple networks, Transp. Sci. 5 (1971), 212-221.
- L.K. Hua, Application of mathematical models to wheat harvesting, Chinese Mathematics 2 (1962), 539-560.
- M. Jeger, O. Kariv, Algorithms for finding \(p\)-centers on a weighted tree (for relatively small \(p\)), Networks 15 (1985), 381-389. https://doi.org/10.1002/net.3230150308
- O. Kariv, S.L. Hakimi, An algorithmic approach to network location problems. I: The \(p\)-centers, SIAM J. Appl. Math. 37 (1979), 513-538.
- O. Kariv, S.L. Hakimi, An algorithmic approach to network location problems. II: The \(p\)-medians, SIAM J. Appl. Math. 37 (1979), 539-560.
- T.U. Kim, T.J. Lowe, J.E. Ward, Locating a median subtree on a network, INFOR: Information Systems and Operational Research 29 (1991), 153-166.
- R.F. Love, J.G. Morris, G.O. Wesolowsky, Facilities Location: Models & Methods, North-Holland, 1988.
- N. Megiddo, The weighted Euclidean 1-center problem, Math. Oper. Res. 8 (1983), 498-504.
- E. Minieka, N.H. Patel, On finding the core of a tree with a specified length, J. Algorithms 4 (1983), 345-352.
- C.A. Morgan, P.J. Slater, A linear algorithm for a core of a tree, J. Algorithms 1 (1980), 247-258.
- S. Nickel, J. Puerto, A unified approach to network location problems, Networks 34 (1999), 283-290.
- J. Puerto, F. Ricca, A. Scozzari, Extensive facility location problems on networks: an updated review, TOP 26 (2018), 187-226. https://doi.org/10.1007/s11750-018-0476-5
- A. Schöbel, Locating Lines and Hyperplanes: Theory and Algorithms, Springer, Berlin, 1999.
- A. Shioura, M. Shigeno, The tree center problems and the relationship with the bottleneck knapsack problems, Networks 29 (1997), 107-110.
- A. Tamir, An \(O(pn^2)\) algorithm for the \(p\)-median and related problems on tree graphs, Oper. Res. Lett. 19 (1996), 59-64. https://doi.org/10.1016/0167-6377(96)00021-1
- A. Tamir, J. Puerto, D. Pérez-Brito, The centdian subtree on tree networks, Discret. Appl. Math. 118 (2002), 263-278. https://doi.org/10.1016/S0166-218X(01)00199-8
- M. Zaferanieh, J. Fathali, Finding a core of a tree with pos/neg weight, Math. Methods Oper. Res. 76 (2012), 147-160. https://doi.org/10.1007/s00186-012-0394-5
- Tran Hoai Ngoc Nhan
- Faculty of Basic Sciences, Vinh Long University of Technology Education, Vinh Long, Vietnam
- Nguyen Thanh Hung
- Department of Mathematics, Teacher College, Can Tho University, Can Tho, Vietnam
- Kien Trung Nguyen (corresponding author)
- Department of Mathematics, Teacher College, Can Tho University, Can Tho, Vietnam
- Communicated by P.A. Cojuhari.
- Received: 2023-01-28.
- Accepted: 2023-08-01.
- Published online: 2023-10-27.
