American Institute of Mathematical Sciences

Advanced
  • 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
January  2021, 17(1): 221-232. doi: 10.3934/jimo.2019108

Inverse group 1-median problem on trees

Kien Trung Nguyen 1, , Vo Nguyen Minh Hieu 1, and  Van Huy Pham 2,,

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

Received  October 2018 Revised  April 2019 Published  September 2019

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: Group median, inverse optimization, tree, complexity, parameterization.
Mathematics Subject Classification: 90B10, 90B80, 90C27.
Citation: Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108
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.  Google Scholar

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

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

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

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

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

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

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

[9]

Z. Drezner and H. W. Hamacher, Facility Location Applications and Theory, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-642-56082-8.  Google Scholar

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

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

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

[13]

A. J. Goldman, Optimal center location in simple networks, Transportation Sci., 5 (1971), 212-221.  doi: 10.1287/trsc.5.2.212.  Google Scholar

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

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

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

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

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

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

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

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

[22]

S. Nickel and J. Puerto, Location Theory - A unified approach, Springer, Berlin, 2004. doi: 10.1007/3-540-27640-8.  Google Scholar

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

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

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

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

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

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

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

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

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

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.  Google Scholar

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

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

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

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

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

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

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

[9]

Z. Drezner and H. W. Hamacher, Facility Location Applications and Theory, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-642-56082-8.  Google Scholar

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

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

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

[13]

A. J. Goldman, Optimal center location in simple networks, Transportation Sci., 5 (1971), 212-221.  doi: 10.1287/trsc.5.2.212.  Google Scholar

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

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

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

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

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

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

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

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

[22]

S. Nickel and J. Puerto, Location Theory - A unified approach, Springer, Berlin, 2004. doi: 10.1007/3-540-27640-8.  Google Scholar

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

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

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

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

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

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

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

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

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

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

Download full-size image

Download as 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 -
Table Options

Download as excel

$ 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 Options

Download as excel

Table 3.  Cost values at breakpoints
$ t $ 8 10 18 20
$ C(t) $ 46 44 49 56
Table Options

Download as excel

$ t $ 8 10 18 20
$ C(t) $ 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

  • PDF downloads (179)
  • HTML views (571)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences