TY  - JOUR
ID  - Nhan2024
LB  - Nhan2024
AU  - Nhan, Tran Hoai Ngoc
AU  - Hung, Nguyen Thanh
AU  - Nguyen, Kien Trung
TI  - The extensive 1-median problem with radius on networks
ST  - The extensive 1-median problem with radius on networks
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2024
VL  - 44
IS  - 1
SP  - 135
EP  - 149
DO  - https://doi.org/10.7494/OpMath.2024.44.1.135
UR  - https://doi.org/10.7494/OpMath.2024.44.1.135
AB  - 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.
KW  - extensive facility
KW  - median problem
KW  - tree
KW  - convex
SN  - 1232-9274
ER  -