
-
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] |
Alba Málaga Sabogal, Serge Troubetzkoy. Minimality of the Ehrenfest wind-tree model. Journal of Modern Dynamics, 2016, 10: 209-228. doi: 10.3934/jmd.2016.10.209 |
[2] |
Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021 |
[3] |
Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 |
[4] |
Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637 |
[5] |
Zhimin Chen, Kaihui Liu, Xiuxiang Liu. Evaluating vaccination effectiveness of group-specific fractional-dose strategies. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021062 |
[6] |
Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 |
[7] |
Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021 doi: 10.3934/mcrf.2021008 |
[8] |
Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023 |
[9] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
[10] |
Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024 |
[11] |
Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021 doi: 10.3934/naco.2021008 |
[12] |
Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 |
[13] |
Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]