# American Institute of Mathematical Sciences

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] Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial & Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629 [2] Liping Zhang, Soon-Yi Wu. Robust solutions to Euclidean facility location problems with uncertain data. Journal of Industrial & Management Optimization, 2010, 6 (4) : 751-760. doi: 10.3934/jimo.2010.6.751 [3] Gbeminiyi John Oyewole, Olufemi Adetunji. Solving the facility location and fixed charge solid transportation problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1557-1575. doi: 10.3934/jimo.2020034 [4] Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 [5] Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044 [6] Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $k$-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056 [7] Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215 [8] Zhimin Liu, Shaojian Qu, Hassan Raza, Zhong Wu, Deqiang Qu, Jianhui Du. Two-stage mean-risk stochastic mixed integer optimization model for location-allocation problems under uncertain environment. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020094 [9] J. F. Padial. Existence and estimate of the location of the free-boundary for a non local inverse elliptic-parabolic problem arising in nuclear fusion. Conference Publications, 2011, 2011 (Special) : 1176-1185. doi: 10.3934/proc.2011.2011.1176 [10] Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $l_1$ norm measure. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061 [11] Philip Trautmann, Boris Vexler, Alexander Zlotnik. Finite element error analysis for measure-valued optimal control problems governed by a 1D wave equation with variable coefficients. Mathematical Control & Related Fields, 2018, 8 (2) : 411-449. doi: 10.3934/mcrf.2018017 [12] Kewei Zhang. On equality of relaxations for linear elastic strains. Communications on Pure & Applied Analysis, 2002, 1 (4) : 565-573. doi: 10.3934/cpaa.2002.1.565 [13] Qinglan Xia, Shaofeng Xu. On the ramified optimal allocation problem. Networks & Heterogeneous Media, 2013, 8 (2) : 591-624. doi: 10.3934/nhm.2013.8.591 [14] Monika Muszkieta. A variational approach to edge detection. Inverse Problems & Imaging, 2016, 10 (2) : 499-517. doi: 10.3934/ipi.2016009 [15] Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391 [16] Liming Zhang, Tao Qian, Qingye Zeng. Edge detection by using rotational wavelets. Communications on Pure & Applied Analysis, 2007, 6 (3) : 899-915. doi: 10.3934/cpaa.2007.6.899 [17] Dmitry Dolgopyat, Dmitry Jakobson. On small gaps in the length spectrum. Journal of Modern Dynamics, 2016, 10: 339-352. doi: 10.3934/jmd.2016.10.339 [18] Emmanuel Schenck. Exponential gaps in the length spectrum. Journal of Modern Dynamics, 2020, 16: 207-223. doi: 10.3934/jmd.2020007 [19] Giuseppe Buttazzo, Serena Guarino Lo Bianco, Fabrizio Oliviero. Optimal location problems with routing cost. Discrete & Continuous Dynamical Systems, 2014, 34 (4) : 1301-1317. doi: 10.3934/dcds.2014.34.1301 [20] Lotfi Tadj, Zhe George Zhang, Chakib Tadj. A queueing analysis of multi-purpose production facility's operations. Journal of Industrial & Management Optimization, 2011, 7 (1) : 19-30. doi: 10.3934/jimo.2011.7.19

2019 Impact Factor: 1.366