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]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031
[2]

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
[3]

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
[4]

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
[5]

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
[6]

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

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
[8]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[9]

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
[10]

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
[11]

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
[12]

Yi An, Bo Li, Lei Wang, Chao Zhang, Xiaoli Zhou. Calibration of a 3D laser rangefinder and a camera based on optimization solution. Journal of Industrial & Management Optimization, 2021, 17 (1) : 427-445. doi: 10.3934/jimo.2019119
[13]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100
[14]

Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109
[15]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[16]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[17]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073
[18]

Noriyoshi Fukaya. Uniqueness and nondegeneracy of ground states for nonlinear Schrödinger equations with attractive inverse-power potential. Communications on Pure & Applied Analysis, 2021, 20 (1) : 121-143. doi: 10.3934/cpaa.2020260
[19]

Kai Yang. Scattering of the focusing energy-critical NLS with inverse square potential in the radial case. Communications on Pure & Applied Analysis, 2021, 20 (1) : 77-99. doi: 10.3934/cpaa.2020258
[20]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (123)
  • HTML views (507)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences