
-
Previous Article
Multi-stage distributionally robust optimization with risk aversion
- JIMO Home
- This Issue
-
Next Article
A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size
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 |
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.
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. |
show all references
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. |

1 | 2 | 3 | 5 | |
0 | 0 | 0 | 0 | |
0 | 0 | 0 | - | |
0 | 0 | 0 | 3 | |
0 | 0 | 16 | - |
1 | 2 | 3 | 5 | |
0 | 0 | 0 | 0 | |
0 | 0 | 0 | - | |
0 | 0 | 0 | 3 | |
0 | 0 | 16 | - |
8 | 10 | 18 | 20 | |
46 | 44 | 49 | 56 |
8 | 10 | 18 | 20 | |
46 | 44 | 49 | 56 |
[1] |
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, 2020 doi: 10.3934/jimo.2021017 |
[2] |
Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020 doi: 10.3934/nhm.2020031 |
[3] |
Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021006 |
[4] |
Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167 |
[5] |
Dandan Cheng, Qian Hao, Zhiming Li. Scale pressure for amenable group actions. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021008 |
[6] |
Laurent Di Menza, Virginie Joanne-Fabre. An age group model for the study of a population of trees. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020464 |
[7] |
Qiao Liu. Local rigidity of certain solvable group actions on tori. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 553-567. doi: 10.3934/dcds.2020269 |
[8] |
Meihua Dong, Keonhee Lee, Carlos Morales. Gromov-Hausdorff stability for group actions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1347-1357. doi: 10.3934/dcds.2020320 |
[9] |
Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 |
[10] |
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 |
[11] |
Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050 |
[12] |
Yi-Hsuan Lin, Gen Nakamura, Roland Potthast, Haibing Wang. Duality between range and no-response tests and its application for inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020072 |
[13] |
Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074 |
[14] |
Xinlin Cao, Huaian Diao, Jinhong Li. Some recent progress on inverse scattering problems within general polyhedral geometry. Electronic Research Archive, 2021, 29 (1) : 1753-1782. doi: 10.3934/era.2020090 |
[15] |
Shumin Li, Masahiro Yamamoto, Bernadette Miara. A Carleman estimate for the linear shallow shell equation and an inverse source problem. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 367-380. doi: 10.3934/dcds.2009.23.367 |
[16] |
Jianli Xiang, Guozheng Yan. The uniqueness of the inverse elastic wave scattering problem based on the mixed reciprocity relation. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021004 |
[17] |
Stanislav Nikolaevich Antontsev, Serik Ersultanovich Aitzhanov, Guzel Rashitkhuzhakyzy Ashurova. An inverse problem for the pseudo-parabolic equation with p-Laplacian. Evolution Equations & Control Theory, 2021 doi: 10.3934/eect.2021005 |
[18] |
Hongyan Guo. Automorphism group and twisted modules of the twisted Heisenberg-Virasoro vertex operator algebra. Electronic Research Archive, , () : -. doi: 10.3934/era.2021008 |
[19] |
Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115 |
[20] |
Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098 |
2019 Impact Factor: 1.366
Tools
Article outline
Figures and Tables
[Back to Top]