The extensive 1-median problem with radius on networks

• Autorzy: Nhan Tran Hoai Ngoc , Hung Nguyen Thanh , Nguyen Kien Trung

Identyfikatory

DOI

10.7494/OpMath.2024.44.1.135

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

extensive facility; median problem; tree; convex

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2024
• Tom: Vol. 44, no. 1
• Strony: 135--149
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Nhan Tran Hoai Ngoc

• Faculty of Basic Sciences, Vinh Long University of Technology Education, Vinh Long, Vietnam

autor

Hung Nguyen Thanh

• Department of Mathematics, Teacher College, Can Tho University, Can Tho, Vietnam

autor

Nguyen Kien Trung

• Department of Mathematics, Teacher College, Can Tho University, Can Tho, Vietnam

Bibliografia

• [1] 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.
• [2] B. Bhattacharya, Q. Shi, A. Tamir, Optimal algorithms for the path/tree-shaped facility location problems in trees, Algorithmica 55 (2009), 601–618.
• [3] R. Chandrasekaran, The weighted euclidean 1-center problem, Oper. Res. Lett. 1 (1982), 111–112.
• [4] Z. Drezner, H.W. Hamacher, Facility Location – Applications and Theory, Springer-Verlag, Berlin, Heidelberg, 2002.
• [5] H.A. Eiselt, V. Marianov, Foundations of Location Analysis, Springer, 2011.
• [6] A.J. Goldman, Optimal center location in simple networks, Transp. Sci. 5 (1971), 212–221.
• [7] L.K. Hua, Application of mathematical models to wheat harvesting, Chinese Mathematics 2 (1962), 539–560.
• [8] M. Jeger, O. Kariv, Algorithms for finding p-centers on a weighted tree (for relatively small p), Networks 15 (1985), 381–389.
• [9] O. Kariv, S.L. Hakimi, An algorithmic approach to network location problems. I: The p-centers, SIAM J. Appl. Math. 37 (1979), 513–538.
• [10] O. Kariv, S.L. Hakimi, An algorithmic approach to network location problems. II: The p-medians, SIAM J. Appl. Math. 37 (1979), 539–560.
• [11] 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.
• [12] R.F. Love, J.G. Morris, G.O. Wesolowsky, Facilities Location: Models & Methods, North-Holland, 1988.
• [13] N. Megiddo, The weighted Euclidean 1-center problem, Math. Oper. Res. 8 (1983), 498–504.
• [14] E. Minieka, N.H. Patel, On finding the core of a tree with a specified length, J. Algorithms 4 (1983), 345–352.
• [15] C.A. Morgan, P.J. Slater, A linear algorithm for a core of a tree, J. Algorithms 1 (1980), 247–258.
• [16] S. Nickel, J. Puerto, A unified approach to network location problems, Networks 34 (1999), 283–290.
• [17] J. Puerto, F. Ricca, A. Scozzari, Extensive facility location problems on networks: an updated review, TOP 26 (2018), 187–226.
• [18] A. Schöbel, Locating Lines and Hyperplanes: Theory and Algorithms, Springer, Berlin, 1999.
• [19] A. Shioura, M. Shigeno, The tree center problems and the relationship with the bottleneck knapsack problems, Networks 29 (1997), 107–110.
• [20] A. Tamir, An O(pn2) algorithm for the p-median and related problems on tree graphs, Oper. Res. Lett. 19 (1996), 59–64.
• [21] A. Tamir, J. Puerto, D. Pérez-Brito, The centdian subtree on tree networks, Discret. Appl. Math. 118 (2002), 263–278.
• [22] M. Zaferanieh, J. Fathali, Finding a core of a tree with pos/neg weight, Math. Methods Oper. Res. 76 (2012), 147–160.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)