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]

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]

Copyright © 2021 American Institute of Mathematical Sciences