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  January 2021 Early access  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 and 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.

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

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 and Management Optimization, 2022, 18 (2) : 1247-1259. doi: 10.3934/jimo.2021017
[2]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks and Heterogeneous Media, 2021, 16 (1) : 1-29. doi: 10.3934/nhm.2020031
[3]

Afaf Bouharguane, Pascal Azerad, Frédéric Bouchette, Fabien Marche, Bijan Mohammadi. Low complexity shape optimization & a posteriori high fidelity validation. Discrete and Continuous Dynamical Systems - B, 2010, 13 (4) : 759-772. doi: 10.3934/dcdsb.2010.13.759
[4]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[5]

Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003
[6]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[7]

Li-Fang Dai, Mao-Lin Liang, Wei-Yuan Ma. Optimization problems on the rank of the solution to left and right inverse eigenvalue problem. Journal of Industrial and Management Optimization, 2015, 11 (1) : 171-183. doi: 10.3934/jimo.2015.11.171
[8]

Lekbir Afraites, Chorouk Masnaoui, Mourad Nachaoui. Shape optimization method for an inverse geometric source problem and stability at critical shape. Discrete and Continuous Dynamical Systems - S, 2022, 15 (1) : 1-21. doi: 10.3934/dcdss.2021006
[9]

Lluís Alsedà, David Juher, Pere Mumbrú. Minimal dynamics for tree maps. Discrete and Continuous Dynamical Systems, 2008, 20 (3) : 511-541. doi: 10.3934/dcds.2008.20.511
[10]

Jonathan Hoseana, Franco Vivaldi. Geometrical properties of the mean-median map. Journal of Computational Dynamics, 2020, 7 (1) : 83-121. doi: 10.3934/jcd.2020004
[11]

Rodrigo Abarzúa, Nicolas Thériault, Roberto Avanzi, Ismael Soto, Miguel Alfaro. Optimization of the arithmetic of the ideal class group for genus 4 hyperelliptic curves over projective coordinates. Advances in Mathematics of Communications, 2010, 4 (2) : 115-139. doi: 10.3934/amc.2010.4.115
[12]

Mohammed Al-Azba, Zhaohui Cen, Yves Remond, Said Ahzi. Air-Conditioner Group Power Control Optimization for PV integrated Micro-grid Peak-shaving. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3165-3181. doi: 10.3934/jimo.2020112
[13]

Qun Lin, Ryan Loxton, Kok Lay Teo. The control parameterization method for nonlinear optimal control: A survey. Journal of Industrial and Management Optimization, 2014, 10 (1) : 275-309. doi: 10.3934/jimo.2014.10.275
[14]

Benedict Leimkuhler, Charles Matthews, Tiffany Vlaar. Partitioned integrators for thermodynamic parameterization of neural networks. Foundations of Data Science, 2019, 1 (4) : 457-489. doi: 10.3934/fods.2019019
[15]

C. M. Groothedde, J. D. Mireles James. Parameterization method for unstable manifolds of delay differential equations. Journal of Computational Dynamics, 2017, 4 (1&2) : 21-70. doi: 10.3934/jcd.2017002
[16]

Claude Carlet. Parameterization of Boolean functions by vectorial functions and associated constructions. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022013
[17]

Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334
[18]

Huajun Tang, T. C. Edwin Cheng, Chi To Ng. A note on the subtree ordered median problem in networks based on nestedness property. Journal of Industrial and Management Optimization, 2012, 8 (1) : 41-49. doi: 10.3934/jimo.2012.8.41
[19]

Matthew B. Rudd, Heather A. Van Dyke. Median values, 1-harmonic functions, and functions of least gradient. Communications on Pure and Applied Analysis, 2013, 12 (2) : 711-719. doi: 10.3934/cpaa.2013.12.711
[20]

Stefano Galatolo. Orbit complexity and data compression. Discrete and Continuous Dynamical Systems, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (395)
  • HTML views (843)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy