Article Contents
Article Contents

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

• * Corresponding author: Jafar Fathali
• 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.

Mathematics Subject Classification: Primary: 90B80; Secondary: 90B06.

 Citation:

• Figure 1.  The tree $T$ with 10 verteices

Table 1.  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

Table 2.  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

Table 3.  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

Table 4.  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
•  [1] B. Alizadeh, E. Afrashteh and F. Baroughi, Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks, Journal of Optimization Theory and Applications, 178 (2018), 914-934.  doi: 10.1007/s10957-018-1334-1. [2] B. Alizadeh, R. E. Burkard and U. Pferschy, Inverse 1-center location problems with edge length augmentation on trees, Computing, 86 (2009), 331-343.  doi: 10.1007/s00607-009-0070-7. [3] B. Alizadeh and R. E. Burkard, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58 (2011), 190-200.  doi: 10.1002/net.20427. [4] B. Alizadeh and R. Etemad, Optimal algorithms for inverse vertex obnoxious center location problems on graphs, Theoretical Computer Science, 707 (2018), 36-45.  doi: 10.1016/j.tcs.2017.10.001. [5] M. Barbati and C. Piccolo, Equality measures properties for location problems, Optimization Letters, 10 (2015), 903-920.  doi: 10.1007/s11590-015-0968-2. [6] O. Berman, Z. Drezner, A. Tamir and G. O. Wesolowsky, Optimal location with equitable loads, Annals of Operations Research, 167 (2009), 307-325.  doi: 10.1007/s10479-008-0339-9. [7] R. W. Bulterman, F. W. Van-Der-Sommen, G. Zwaan T. Verhoeff, A. J. M. Van-Gasteren and W. H. J. Feijen, On computing a longest path in a tree, Information Processing Letters, 81 (2002), 93-96.  doi: 10.1016/S0020-0190(01)00198-3. [8] R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang, Inverse median problems, Discrete Optimization, 1 (2004), 23-39.  doi: 10.1016/j.disopt.2004.03.003. [9] R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang, The inverse 1-median problem on a cycle, Discrete Optimization, 5 (2008), 242-253.  doi: 10.1016/j.disopt.2006.11.008. [10] M. C. Cai, X. G. Yang and J. Zhang, The complexity analysis of the inverse center location problem, Journal of Global Optimization, 15 (1999), 213-218.  doi: 10.1023/A:1008360312607. [11] M. Davoodi, k-Balanced Center Location problem: A new multi-objective facility location problem, Computers & Operations Research, 105 (2019), 68-84.  doi: 10.1016/j.cor.2019.01.009. [12] H. A. Eiselt and G. Laporte, Objectives in Location Problems, In: Facility Location: A Survey of Applications and Methods (eds. Z. Drezner), Springer, Berlin, (1995), 151–180. doi: 10.1007/978-1-4612-5355-6. [13] J. Fathali and M. Zaferanieh, The balanced 2-median and 2-maxian problems on a tree, arXiv preprint, arXiv: 1803.10332, 2018. [14] M. Galavii, The inverse 1-median problem on a tree and on a path, Electronic Notes in Discrete Mathematics, 36 (2010), 1241-1248.  doi: 10.1016/j.endm.2010.05.157. [15] M. Gavalec and O. Hudec, Balanced location on a graph, Optimization, 35 (1995), 367-372.  doi: 10.1080/02331939508844156. [16] X. C. Guan and B. W. Zhang, Inverse 1-median problem on trees under weighted Hamming distance, Journal of Global Optimization, 54 (2012), 75-82.  doi: 10.1007/s10898-011-9742-x. [17] G. Y. Handler, Minimax location of a facility in an undirected tree networks, Transportation Sci., 7 (1973), 287-293.  doi: 10.1287/trsc.7.3.287. [18] C. Heuberger, Inverse combinatorial optimization: a survey on problems, methods, and results, J. Comb. Optim., 8 (2004), 329-361.  doi: 10.1023/B:JOCO.0000038914.26975.9b. [19] M. Landete and A. Marin, Looking for edge-equitable spanning trees, Computers & Operations Research, 41 (2014), 44-52.  doi: 10.1016/j.cor.2013.07.023. [20] M. A. Lejeune and S. Y. Prasad, Effectiveness-equity models for facility location problems on tree networks, Networks, 62 (2013), 243-254.  doi: 10.1002/net.21510. [21] A. Marin, The discrete facility location problem with balanced allocation of customers, European Journal of Operational Research, 210 (2011), 27-38.  doi: 10.1016/j.ejor.2010.10.012. [22] M. T. Marsh and D. A. Schilling, Equity measurement in facility location analysis: a review and framework, European Journal of Operational Research, 74 (1994), 1-17.  doi: 10.1016/0377-2217(94)90200-3. [23] P. B. Mirchandani and R. Francis, Discrete Location Theory, J. Wiley, 1990. [24] M. Nazari, J. Fathali, M. Nazari and S. M. Varedi-Koulaei, Inverse of backup 2-median problems with variable edge lengths and vertex weight on trees and variable coordinates on the plane, Production and Operations Management, 9 (2018), 115-137. [25] K. T. Nguyen, Inverse 1-median problem on block graphs with variable vertex weights, Journal of Optimization Theory and Applications, 168 (2016), 944-957.  doi: 10.1007/s10957-015-0829-2. [26] K. T. Nguyen and A. R. Sepasian, The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, Journal of Combinatorial Optimization, 32 (2016), 872-884.  doi: 10.1007/s10878-015-9907-5. [27] S. Omidi, J. Fathali and M. Nazari, Inverse and reverse balanced facility location problems with variable edge lengths on trees, OPSEARCH, 57 (2020), 261-273.  doi: 10.1007/s12597-019-00428-6. [28] V. H. Pham, K. T. Nguyen and T.T. Le, A linear time algorithm for balance vertices on trees, Discrete Optimization, 32 (2018), 37-42.  doi: 10.1016/j.disopt.2018.11.001. [29] T. Sayar, J. Fathali and M. Ghiyasi, The problem of balancing allocation with regard to the efficiency of servers, Iranian Journal of Operations Research, 9 (2018), 29-47. [30] A. R. Sepasian and F. Rahbarnia, An O(nlogn) algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions, Optimization, 64 (2015), 595-602.  doi: 10.1080/02331934.2013.783033.

Figures(1)

Tables(4)