Article Contents
Article Contents

# Inverse group 1-median problem on trees

• * Corresponding author: Van Huy Pham
• In location theory, group median generalizes the concepts of both median and center. We address in this paper the problem of modifying vertex weights of a tree at minimum total cost so that a prespecified vertex becomes a group 1-median with respect to the new weights. We call this problem the inverse group 1-median on trees. To solve the problem, we first reformulate the optimality criterion for a vertex being a group 1-median of the tree. Based on this result, we prove that the problem is $NP$-hard. Particularly, the corresponding problem with exactly two groups is however solvable in $O(n^2\log n)$ time, where $n$ is the number of vertices in the tree.

Mathematics Subject Classification: 90B10, 90B80, 90C27.

 Citation:

• Figure 1.  An instance of the inverse 2-group 1-median problem on trees

Table 1.  An instance of the inverse 2-group 1-median problem

 $j$ 1 2 3 5 $\bar{q}^1_j$ 0 0 0 0 $\bar{q}^2_j$ 0 0 0 - $\bar{p}^1_j$ 0 0 0 3 $\bar{p}^2_j$ 0 0 16 -

Table 2.  An instance of the subproblem $(P^1_{v^1_4})$

Table 3.  Cost values at breakpoints

 $t$ 8 10 18 20 $C(t)$ 46 44 49 56
•  [1] B. Alizadeh, E. Afrashteh and F. Baroughi, Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks, J. Optim. Theory Appl., 178 (2018), 914-934.  doi: 10.1007/s10957-018-1334-1. [2] 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. [3] B. Alizadeh and R. E. Burkard, Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees, Discrete Appl. Math., 159 (2011), 706-716.  doi: 10.1016/j.dam.2011.01.009. [4] B. Alizadeh and R. E. Burkard, A linear time algorithm for inverse obnoxious center location problems on networks, CEJOR Cent. Eur. J. Oper. Res., 21 (2013), 585-594.  doi: 10.1007/s10100-012-0248-5. [5] F. B. Bonab, R. E. Burkard and E. Gassner, Inverse p-median problems with variable edge lengths, Math. Methods Oper. Res., 73 (2011), 263-280.  doi: 10.1007/s00186-011-0346-5. [6] R. E. Burkard, M. Galavii and E. Gassner, The inverse Fermat-Weber problem, European J. Oper. Res., 206 (2010), 11-17.  doi: 10.1016/j.ejor.2010.01.046. [7] R. E. Burkard, C. Pleschiutschnig and J. Zhang, Inverse median problems, Discrete Optim., 1 (2004), 23-39.  doi: 10.1016/j.disopt.2004.03.003. [8] M. C. Cai, X. G. Yang and J. Z. Zhang, The complexity analysis of the inverse center location problem, J. Global Optim., 15 (1999), 213-218.  doi: 10.1023/A:1008360312607. [9] Z. Drezner and H. W. Hamacher, Facility Location Applications and Theory, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-642-56082-8. [10] M. Galavii, The inverse 1-median problem on a tree and on a path, Electron Notes in Discrete Math., 36 (2010), 1241-1248.  doi: 10.1016/j.endm.2010.05.157. [11] M. R. Garey, and D. S. Johnson, Computers and intractability: A guide to the theory of $NP$-completeness, W. H. Freeman and Co., San Francisco, CA, 1979. [12] E. Gassner, An inverse approach to convex ordered median problems in trees, J. Comb. Optim., 23 (2012), 261-273.  doi: 10.1007/s10878-010-9353-3. [13] A. J. Goldman, Optimal center location in simple networks, Transportation Sci., 5 (1971), 212-221.  doi: 10.1287/trsc.5.2.212. [14] X. Guan and B. Zhang, Inverse 1-median problem on trees under weighted Hamming distance, J. Global Optim., 54 (2012), 75-82.  doi: 10.1007/s10898-011-9742-x. [15] S. K. Gupta and A. P. Punnen, Group centre and group median of a network., European J. Oper. Res., 38 (1989), 94-97.  doi: 10.1016/0377-2217(89)90473-6. [16] S. K. Gupta and A. P. Punnen, Group centre and group median of a tree, European J. Oper. Res., 65 (1993), 400-406.  doi: 10.1016/0377-2217(93)90119-8. [17] H. W. Hamacher, Mathematische L$\ddot{\text{o}}$sungsverfahren f$\ddot{\text{o}}$r planare Standortprobleme, Verlag Vieweg, Wiesbaden, 1995. doi: 10.1007/978-3-663-01968-8. [18] O. Kariv and S. L. Hakimi, An algorithmic approach to network location problems.Ⅰ: The p-centers, SIAM J. Appl. Math., 37 (1979), 513-538.  doi: 10.1137/0137040. [19] O. Kariv and S. L. Hakimi, An algorithmic approach to network location problems. Ⅱ: The p-medians, SIAM J. Appl. Math., 37 (1979), 539-560.  doi: 10.1137/0137041. [20] I. Keshtkar and M. Ghiyasvand, Inverse quickest center location problem on a tree, Discrete Appl. Math., 260 (2019), 188-202.  doi: 10.1016/j.dam.2019.01.001. [21] N. Megiddo, Linear-time algorithms for linear programming in $\mathbb{R}^3$ and related problems, SIAM J. Comput., 12 (1983), 759-776.  doi: 10.1137/0212052. [22] S. Nickel and J. Puerto, Location Theory - A unified approach, Springer, Berlin, 2004. doi: 10.1007/3-540-27640-8. [23] K. T. Nguyen, Inverse 1-median problem on block graphs with variable vertex weights, J. Optim. Theory Appl., 168 (2016), 944-957.  doi: 10.1007/s10957-015-0829-2. [24] K. T. Nguyen, Some polynomially solvable cases of the inverse ordered 1-median problem on trees, Filomat, 31 (2017), 3651-3664.  doi: 10.2298/FIL1712651N. [25] K. T. Nguyen and L. Q. Anh, Inverse k-centrum problem on trees with variable vertex weights, Math. Methods Oper. Res., 82 (2015), 19-30.  doi: 10.1007/s00186-015-0502-4. [26] K. T. Nguyen and A. Chassein, The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance, European J. Oper. Res., 247 (2015), 774-781.  doi: 10.1016/j.ejor.2015.06.064. [27] K. T. Nguyen and A. R. Sepasian, The inverse 1-center problem on trees under Chebyshev norm and Hamming distance, J. Comb. Optim., 32 (2016), 872-884.  doi: 10.1007/s10878-015-9907-5. [28] K. T. Nguyen, The inverse 1-center problem on cycles with variable edge lengths, CEJOR Cent. Eur. J. Oper. Res., 27 (2019), 263-274.  doi: 10.1007/s10100-017-0509-4. [29] K. T. Nguyen, N. T. Huong and T. H. Nguyen, On the complexity of inverse convex ordered 1-median problem on the plane and on tree networks, Math. Methods Oper. Res., 88 (2018), 147-159.  doi: 10.1007/s00186-018-0632-6. [30] K. T. Nguyen, N. T. Huong and T. H. Nguyen, Combinatorial algorithms for the uniform-cost inverse 1-center problem on weighted trees, Acta Mathematica Vietnamica, (2018), 1–19. doi: 10.1007/s40306-018-0286-8. [31] J. Puerto, F. Ricca and A. Scozzari, Extensive facility location problems on networks: an updated review, TOP, 26 (2018), 187-266.  doi: 10.1007/s11750-018-0476-5.

Figures(1)

Tables(3)