Inverse group 1-median problem on trees

Kien Trung Nguyen; Vo Nguyen Minh Hieu; Van Huy Pham

doi:10.3934/jimo.2019108

Article Contents

2021, Volume 17, Issue 1: 221-232. Doi: 10.3934/jimo.2019108

This issue Previous Article A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size Next Article Multi-stage distributionally robust optimization with risk aversion

Inverse group 1-median problem on trees

1.
Department of Mathematics, Teacher College, Can Tho University, Can Tho, Vietnam
2.
AI Lab, Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City, Vietnam

^* Corresponding author: Van Huy Pham
^* Corresponding author: Van Huy Pham

Received: September 30, 2018

Revised: March 31, 2019

Early access: September 2019

Published: January 2021

Abstract Full Text(HTML) Figure(1) / Table(3) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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	-

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Table 3. Cost values at breakpoints

$ t $	8	10	18	20
$ C(t) $	46	44	49	56

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[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.