# American Institute of Mathematical Sciences

• Previous Article
Decision-making in a retailer-led closed-loop supply chain involving a third-party logistics provider
• JIMO Home
• This Issue
• Next Article
Performance analysis and optimization research of multi-channel cognitive radio networks with a dynamic channel vacation scheme
doi: 10.3934/jimo.2021017

## Inverse single facility location problem on a tree with balancing on the distance of server to clients

 Faculty of Mathematical Sciences, Shahrood University of Technology, University Blvd., Shahrood, Iran

* Corresponding author: Jafar Fathali

Received  June 2020 Revised  November 2020 Published  December 2020

We introduce a case of inverse single facility location problem on a tree where by minimum modifying in the length of edges, the difference of distances between the farthest and nearest clients to a given facility is minimized. Two cases are considered: bounded and unbounded nonnegative edge lengths. In the unbounded case, we show the problem can be reduced to solve the problem on a star graph. Then an $O(nlogn)$ algorithm is developed to find the optimal solution. For the bounded edge lengths case an algorithm with time complexity $O(n^2)$ is presented.

Citation: Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021017
##### References:

show all references

##### References:
The tree $T$ with 10 verteices
The lengths and costs of changing lengths of edges in tree $T$
 $e_i$ $l_i$ $c_i^+$ $c_i^-$ $e_1=(v_1,v_2)$ 3 1 2 $e_2=(v_2,x)$ 3 3 1 $e_3=(x,v_3)$ 5 2 2 $e_4=(v_3,v_{4})$ 2 1 3 $e_5=(v_{4},v_{5})$ 8 1 4 $e_6=(x,v_{6})$ 1 5 3 $e_7=(v_6,v_7)$ 2 3 1 $e_8=(x,v_{8})$ 3 5 2 $e_9=(v_{8},v_{9})$ 4 3 4 $e_{10}=(v_{9},v_{10})$ 3 4 4
 $e_i$ $l_i$ $c_i^+$ $c_i^-$ $e_1=(v_1,v_2)$ 3 1 2 $e_2=(v_2,x)$ 3 3 1 $e_3=(x,v_3)$ 5 2 2 $e_4=(v_3,v_{4})$ 2 1 3 $e_5=(v_{4},v_{5})$ 8 1 4 $e_6=(x,v_{6})$ 1 5 3 $e_7=(v_6,v_7)$ 2 3 1 $e_8=(x,v_{8})$ 3 5 2 $e_9=(v_{8},v_{9})$ 4 3 4 $e_{10}=(v_{9},v_{10})$ 3 4 4
The edge length bounds of the tree $T$
 $e_i$ $l_i$ $\underline{l_i}$ $\bar{l_i}$ $e_1=(v_1,v_2)$ 3 1 4 $e_2=(v_2,x)$ 3 2 6 $e_3=(x,v_3)$ 5 1 7 $e_4=(v_3,v_{4})$ 2 1 5 $e_5=(v_{4},v_{5})$ 8 4 10 $e_6=(x,v_{6})$ 1 1 4 $e_7=(v_6,v_7)$ 2 1 5 $e_8=(x,v_{8})$ 3 1 7 $e_9=(v_{8},v_{9})$ 4 2 8 $e_{10}=(v_{9},v_{10})$ 3 1 6
 $e_i$ $l_i$ $\underline{l_i}$ $\bar{l_i}$ $e_1=(v_1,v_2)$ 3 1 4 $e_2=(v_2,x)$ 3 2 6 $e_3=(x,v_3)$ 5 1 7 $e_4=(v_3,v_{4})$ 2 1 5 $e_5=(v_{4},v_{5})$ 8 4 10 $e_6=(x,v_{6})$ 1 1 4 $e_7=(v_6,v_7)$ 2 1 5 $e_8=(x,v_{8})$ 3 1 7 $e_9=(v_{8},v_{9})$ 4 2 8 $e_{10}=(v_{9},v_{10})$ 3 1 6
The iterations result for Example 2
 Iteration $P_1$ $P_2$ $C_{P_1}$ $C_{P_2}$ $f_1$ $f_2$ 1 $\{p_1\}$ $\{p_2\}$ $c^-_3=2$ $c^+_6=5$ 8 10 2 $\{p_1\}$ $\{p_2,p_3\}$ $c^-_4=3$ - 11 9 3 $\{p_1,p_4\}$ $\{p_2,p_3\}$ $c^-_5+c^-_8=6$ - 23 7 4 $\{p_1,p_4\}$ $\{p_2,p_3\}$ $c^-_5+c^-_9=16$ - 39 5
 Iteration $P_1$ $P_2$ $C_{P_1}$ $C_{P_2}$ $f_1$ $f_2$ 1 $\{p_1\}$ $\{p_2\}$ $c^-_3=2$ $c^+_6=5$ 8 10 2 $\{p_1\}$ $\{p_2,p_3\}$ $c^-_4=3$ - 11 9 3 $\{p_1,p_4\}$ $\{p_2,p_3\}$ $c^-_5+c^-_8=6$ - 23 7 4 $\{p_1,p_4\}$ $\{p_2,p_3\}$ $c^-_5+c^-_9=16$ - 39 5
The optimal edge lengths for Example 2
 $e_i$ optimal $l_i$ $\underline{l_i}$ $\bar{l_i}$ $e_1=(v_1,v_2)$ 3 1 4 $e_2=(v_2,x)$ 3 2 6 $e_3=(x,v_3)$ 1 1 7 $e_4=(v_3,v_{4})$ 1 1 5 $e_5=(v_{4},v_{5})$ 4 4 10 $e_6=(x,v_{6})$ 1 1 4 $e_7=(v_6,v_7)$ 2 1 5 $e_8=(x,v_{8})$ 1 1 7 $e_9=(v_{8},v_{9})$ 2 2 8 $e_{10}=(v_{9},v_{10})$ 3 1 6
 $e_i$ optimal $l_i$ $\underline{l_i}$ $\bar{l_i}$ $e_1=(v_1,v_2)$ 3 1 4 $e_2=(v_2,x)$ 3 2 6 $e_3=(x,v_3)$ 1 1 7 $e_4=(v_3,v_{4})$ 1 1 5 $e_5=(v_{4},v_{5})$ 4 4 10 $e_6=(x,v_{6})$ 1 1 4 $e_7=(v_6,v_7)$ 2 1 5 $e_8=(x,v_{8})$ 1 1 7 $e_9=(v_{8},v_{9})$ 2 2 8 $e_{10}=(v_{9},v_{10})$ 3 1 6
 [1] Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082 [2] Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171 [3] Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055 [4] Neil S. Trudinger, Xu-Jia Wang. Quasilinear elliptic equations with signed measure. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 477-494. doi: 10.3934/dcds.2009.23.477 [5] Masaharu Taniguchi. Axisymmetric traveling fronts in balanced bistable reaction-diffusion equations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3981-3995. doi: 10.3934/dcds.2020126 [6] Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Existence results and stability analysis for a nonlinear fractional boundary value problem on a circular ring with an attached edge : A study of fractional calculus on metric graph. Networks & Heterogeneous Media, 2021  doi: 10.3934/nhm.2021003 [7] Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020404 [8] Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, 2021, 14 (1) : 89-113. doi: 10.3934/krm.2020050 [9] Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380 [10] Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106 [11] Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164 [12] Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021002 [13] Kengo Nakai, Yoshitaka Saiki. Machine-learning construction of a model for a macroscopic fluid variable using the delay-coordinate of a scalar observable. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1079-1092. doi: 10.3934/dcdss.2020352 [14] Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial & Management Optimization, 2021, 17 (2) : 669-686. doi: 10.3934/jimo.2019128 [15] Gheorghe Craciun, Jiaxin Jin, Casian Pantea, Adrian Tudorascu. Convergence to the complex balanced equilibrium for some chemical reaction-diffusion systems with boundary equilibria. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1305-1335. doi: 10.3934/dcdsb.2020164 [16] Peter Frolkovič, Karol Mikula, Jooyoung Hahn, Dirk Martin, Branislav Basara. Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 865-879. doi: 10.3934/dcdss.2020350 [17] Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108 [18] Harrison Bray. Ergodicity of Bowen–Margulis measure for the Benoist 3-manifolds. Journal of Modern Dynamics, 2020, 16: 305-329. doi: 10.3934/jmd.2020011 [19] Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217 [20] Giulia Luise, Giuseppe Savaré. Contraction and regularizing properties of heat flows in metric measure spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 273-297. doi: 10.3934/dcdss.2020327

2019 Impact Factor: 1.366

## Tools

Article outline

Figures and Tables