
-
Previous Article
Decision-making in a retailer-led closed-loop supply chain involving a third-party logistics provider
- JIMO Home
- This Issue
-
Next Article
Performance analysis and optimization research of multi-channel cognitive radio networks with a dynamic channel vacation scheme
Inverse single facility location problem on a tree with balancing on the distance of server to clients
Faculty of Mathematical Sciences, Shahrood University of Technology, University Blvd., Shahrood, Iran |
We introduce a case of inverse single facility location problem on a tree where by minimum modifying in the length of edges, the difference of distances between the farthest and nearest clients to a given facility is minimized. Two cases are considered: bounded and unbounded nonnegative edge lengths. In the unbounded case, we show the problem can be reduced to solve the problem on a star graph. Then an $ O(nlogn) $ algorithm is developed to find the optimal solution. For the bounded edge lengths case an algorithm with time complexity $ O(n^2) $ is presented.
References:
[1] |
B. Alizadeh, E. Afrashteh and F. Baroughi,
Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks, Journal of Optimization Theory and Applications, 178 (2018), 914-934.
doi: 10.1007/s10957-018-1334-1. |
[2] |
B. Alizadeh, R. E. Burkard and U. Pferschy,
Inverse 1-center location problems with edge length augmentation on trees, Computing, 86 (2009), 331-343.
doi: 10.1007/s00607-009-0070-7. |
[3] |
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. |
[4] |
B. Alizadeh and R. Etemad,
Optimal algorithms for inverse vertex obnoxious center location problems on graphs, Theoretical Computer Science, 707 (2018), 36-45.
doi: 10.1016/j.tcs.2017.10.001. |
[5] |
M. Barbati and C. Piccolo,
Equality measures properties for location problems, Optimization Letters, 10 (2015), 903-920.
doi: 10.1007/s11590-015-0968-2. |
[6] |
O. Berman, Z. Drezner, A. Tamir and G. O. Wesolowsky,
Optimal location with equitable loads, Annals of Operations Research, 167 (2009), 307-325.
doi: 10.1007/s10479-008-0339-9. |
[7] |
R. W. Bulterman, F. W. Van-Der-Sommen, G. Zwaan T. Verhoeff, A. J. M. Van-Gasteren and W. H. J. Feijen,
On computing a longest path in a tree, Information Processing Letters, 81 (2002), 93-96.
doi: 10.1016/S0020-0190(01)00198-3. |
[8] |
R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang,
Inverse median problems, Discrete Optimization, 1 (2004), 23-39.
doi: 10.1016/j.disopt.2004.03.003. |
[9] |
R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang,
The inverse 1-median problem on a cycle, Discrete Optimization, 5 (2008), 242-253.
doi: 10.1016/j.disopt.2006.11.008. |
[10] |
M. C. Cai, X. G. Yang and J. Zhang,
The complexity analysis of the inverse center location problem, Journal of Global Optimization, 15 (1999), 213-218.
doi: 10.1023/A:1008360312607. |
[11] |
M. Davoodi,
k-Balanced Center Location problem: A new multi-objective facility location problem, Computers & Operations Research, 105 (2019), 68-84.
doi: 10.1016/j.cor.2019.01.009. |
[12] |
H. A. Eiselt and G. Laporte, Objectives in Location Problems, In: Facility Location: A Survey of Applications and Methods (eds. Z. Drezner), Springer, Berlin, (1995), 151–180.
doi: 10.1007/978-1-4612-5355-6. |
[13] |
J. Fathali and M. Zaferanieh, The balanced 2-median and 2-maxian problems on a tree, arXiv preprint, arXiv: 1803.10332, 2018. Google Scholar |
[14] |
M. Galavii,
The inverse 1-median problem on a tree and on a path, Electronic Notes in Discrete Mathematics, 36 (2010), 1241-1248.
doi: 10.1016/j.endm.2010.05.157. |
[15] |
M. Gavalec and O. Hudec,
Balanced location on a graph, Optimization, 35 (1995), 367-372.
doi: 10.1080/02331939508844156. |
[16] |
X. C. Guan and B. W. Zhang,
Inverse 1-median problem on trees under weighted Hamming distance, Journal of Global Optimization, 54 (2012), 75-82.
doi: 10.1007/s10898-011-9742-x. |
[17] |
G. Y. Handler,
Minimax location of a facility in an undirected tree networks, Transportation Sci., 7 (1973), 287-293.
doi: 10.1287/trsc.7.3.287. |
[18] |
C. Heuberger,
Inverse combinatorial optimization: a survey on problems, methods, and results, J. Comb. Optim., 8 (2004), 329-361.
doi: 10.1023/B:JOCO.0000038914.26975.9b. |
[19] |
M. Landete and A. Marin,
Looking for edge-equitable spanning trees, Computers & Operations Research, 41 (2014), 44-52.
doi: 10.1016/j.cor.2013.07.023. |
[20] |
M. A. Lejeune and S. Y. Prasad,
Effectiveness-equity models for facility location problems on tree networks, Networks, 62 (2013), 243-254.
doi: 10.1002/net.21510. |
[21] |
A. Marin,
The discrete facility location problem with balanced allocation of customers, European Journal of Operational Research, 210 (2011), 27-38.
doi: 10.1016/j.ejor.2010.10.012. |
[22] |
M. T. Marsh and D. A. Schilling,
Equity measurement in facility location analysis: a review and framework, European Journal of Operational Research, 74 (1994), 1-17.
doi: 10.1016/0377-2217(94)90200-3. |
[23] |
P. B. Mirchandani and R. Francis, Discrete Location Theory, J. Wiley, 1990. |
[24] |
M. Nazari, J. Fathali, M. Nazari and S. M. Varedi-Koulaei, Inverse of backup 2-median problems with variable edge lengths and vertex weight on trees and variable coordinates on the plane, Production and Operations Management, 9 (2018), 115-137. Google Scholar |
[25] |
K. T. Nguyen,
Inverse 1-median problem on block graphs with variable vertex weights, Journal of Optimization Theory and Applications, 168 (2016), 944-957.
doi: 10.1007/s10957-015-0829-2. |
[26] |
K. T. Nguyen and A. R. Sepasian,
The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, Journal of Combinatorial Optimization, 32 (2016), 872-884.
doi: 10.1007/s10878-015-9907-5. |
[27] |
S. Omidi, J. Fathali and M. Nazari,
Inverse and reverse balanced facility location problems with variable edge lengths on trees, OPSEARCH, 57 (2020), 261-273.
doi: 10.1007/s12597-019-00428-6. |
[28] |
V. H. Pham, K. T. Nguyen and T.T. Le,
A linear time algorithm for balance vertices on trees, Discrete Optimization, 32 (2018), 37-42.
doi: 10.1016/j.disopt.2018.11.001. |
[29] |
T. Sayar, J. Fathali and M. Ghiyasi, The problem of balancing allocation with regard to the efficiency of servers, Iranian Journal of Operations Research, 9 (2018), 29-47. Google Scholar |
[30] |
A. R. Sepasian and F. Rahbarnia,
An O(nlogn) algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions, Optimization, 64 (2015), 595-602.
doi: 10.1080/02331934.2013.783033. |
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, Journal of Optimization Theory and Applications, 178 (2018), 914-934.
doi: 10.1007/s10957-018-1334-1. |
[2] |
B. Alizadeh, R. E. Burkard and U. Pferschy,
Inverse 1-center location problems with edge length augmentation on trees, Computing, 86 (2009), 331-343.
doi: 10.1007/s00607-009-0070-7. |
[3] |
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. |
[4] |
B. Alizadeh and R. Etemad,
Optimal algorithms for inverse vertex obnoxious center location problems on graphs, Theoretical Computer Science, 707 (2018), 36-45.
doi: 10.1016/j.tcs.2017.10.001. |
[5] |
M. Barbati and C. Piccolo,
Equality measures properties for location problems, Optimization Letters, 10 (2015), 903-920.
doi: 10.1007/s11590-015-0968-2. |
[6] |
O. Berman, Z. Drezner, A. Tamir and G. O. Wesolowsky,
Optimal location with equitable loads, Annals of Operations Research, 167 (2009), 307-325.
doi: 10.1007/s10479-008-0339-9. |
[7] |
R. W. Bulterman, F. W. Van-Der-Sommen, G. Zwaan T. Verhoeff, A. J. M. Van-Gasteren and W. H. J. Feijen,
On computing a longest path in a tree, Information Processing Letters, 81 (2002), 93-96.
doi: 10.1016/S0020-0190(01)00198-3. |
[8] |
R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang,
Inverse median problems, Discrete Optimization, 1 (2004), 23-39.
doi: 10.1016/j.disopt.2004.03.003. |
[9] |
R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang,
The inverse 1-median problem on a cycle, Discrete Optimization, 5 (2008), 242-253.
doi: 10.1016/j.disopt.2006.11.008. |
[10] |
M. C. Cai, X. G. Yang and J. Zhang,
The complexity analysis of the inverse center location problem, Journal of Global Optimization, 15 (1999), 213-218.
doi: 10.1023/A:1008360312607. |
[11] |
M. Davoodi,
k-Balanced Center Location problem: A new multi-objective facility location problem, Computers & Operations Research, 105 (2019), 68-84.
doi: 10.1016/j.cor.2019.01.009. |
[12] |
H. A. Eiselt and G. Laporte, Objectives in Location Problems, In: Facility Location: A Survey of Applications and Methods (eds. Z. Drezner), Springer, Berlin, (1995), 151–180.
doi: 10.1007/978-1-4612-5355-6. |
[13] |
J. Fathali and M. Zaferanieh, The balanced 2-median and 2-maxian problems on a tree, arXiv preprint, arXiv: 1803.10332, 2018. Google Scholar |
[14] |
M. Galavii,
The inverse 1-median problem on a tree and on a path, Electronic Notes in Discrete Mathematics, 36 (2010), 1241-1248.
doi: 10.1016/j.endm.2010.05.157. |
[15] |
M. Gavalec and O. Hudec,
Balanced location on a graph, Optimization, 35 (1995), 367-372.
doi: 10.1080/02331939508844156. |
[16] |
X. C. Guan and B. W. Zhang,
Inverse 1-median problem on trees under weighted Hamming distance, Journal of Global Optimization, 54 (2012), 75-82.
doi: 10.1007/s10898-011-9742-x. |
[17] |
G. Y. Handler,
Minimax location of a facility in an undirected tree networks, Transportation Sci., 7 (1973), 287-293.
doi: 10.1287/trsc.7.3.287. |
[18] |
C. Heuberger,
Inverse combinatorial optimization: a survey on problems, methods, and results, J. Comb. Optim., 8 (2004), 329-361.
doi: 10.1023/B:JOCO.0000038914.26975.9b. |
[19] |
M. Landete and A. Marin,
Looking for edge-equitable spanning trees, Computers & Operations Research, 41 (2014), 44-52.
doi: 10.1016/j.cor.2013.07.023. |
[20] |
M. A. Lejeune and S. Y. Prasad,
Effectiveness-equity models for facility location problems on tree networks, Networks, 62 (2013), 243-254.
doi: 10.1002/net.21510. |
[21] |
A. Marin,
The discrete facility location problem with balanced allocation of customers, European Journal of Operational Research, 210 (2011), 27-38.
doi: 10.1016/j.ejor.2010.10.012. |
[22] |
M. T. Marsh and D. A. Schilling,
Equity measurement in facility location analysis: a review and framework, European Journal of Operational Research, 74 (1994), 1-17.
doi: 10.1016/0377-2217(94)90200-3. |
[23] |
P. B. Mirchandani and R. Francis, Discrete Location Theory, J. Wiley, 1990. |
[24] |
M. Nazari, J. Fathali, M. Nazari and S. M. Varedi-Koulaei, Inverse of backup 2-median problems with variable edge lengths and vertex weight on trees and variable coordinates on the plane, Production and Operations Management, 9 (2018), 115-137. Google Scholar |
[25] |
K. T. Nguyen,
Inverse 1-median problem on block graphs with variable vertex weights, Journal of Optimization Theory and Applications, 168 (2016), 944-957.
doi: 10.1007/s10957-015-0829-2. |
[26] |
K. T. Nguyen and A. R. Sepasian,
The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, Journal of Combinatorial Optimization, 32 (2016), 872-884.
doi: 10.1007/s10878-015-9907-5. |
[27] |
S. Omidi, J. Fathali and M. Nazari,
Inverse and reverse balanced facility location problems with variable edge lengths on trees, OPSEARCH, 57 (2020), 261-273.
doi: 10.1007/s12597-019-00428-6. |
[28] |
V. H. Pham, K. T. Nguyen and T.T. Le,
A linear time algorithm for balance vertices on trees, Discrete Optimization, 32 (2018), 37-42.
doi: 10.1016/j.disopt.2018.11.001. |
[29] |
T. Sayar, J. Fathali and M. Ghiyasi, The problem of balancing allocation with regard to the efficiency of servers, Iranian Journal of Operations Research, 9 (2018), 29-47. Google Scholar |
[30] |
A. R. Sepasian and F. Rahbarnia,
An O(nlogn) algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions, Optimization, 64 (2015), 595-602.
doi: 10.1080/02331934.2013.783033. |

3 | 1 | 2 | |
3 | 3 | 1 | |
5 | 2 | 2 | |
2 | 1 | 3 | |
8 | 1 | 4 | |
1 | 5 | 3 | |
2 | 3 | 1 | |
3 | 5 | 2 | |
4 | 3 | 4 | |
3 | 4 | 4 |
3 | 1 | 2 | |
3 | 3 | 1 | |
5 | 2 | 2 | |
2 | 1 | 3 | |
8 | 1 | 4 | |
1 | 5 | 3 | |
2 | 3 | 1 | |
3 | 5 | 2 | |
4 | 3 | 4 | |
3 | 4 | 4 |
3 | 1 | 4 | |
3 | 2 | 6 | |
5 | 1 | 7 | |
2 | 1 | 5 | |
8 | 4 | 10 | |
1 | 1 | 4 | |
2 | 1 | 5 | |
3 | 1 | 7 | |
4 | 2 | 8 | |
3 | 1 | 6 |
3 | 1 | 4 | |
3 | 2 | 6 | |
5 | 1 | 7 | |
2 | 1 | 5 | |
8 | 4 | 10 | |
1 | 1 | 4 | |
2 | 1 | 5 | |
3 | 1 | 7 | |
4 | 2 | 8 | |
3 | 1 | 6 |
Iteration | ||||||
1 | 8 | 10 | ||||
2 | - | 11 | 9 | |||
3 | - | 23 | 7 | |||
4 | - | 39 | 5 |
Iteration | ||||||
1 | 8 | 10 | ||||
2 | - | 11 | 9 | |||
3 | - | 23 | 7 | |||
4 | - | 39 | 5 |
optimal |
|||
3 | 1 | 4 | |
3 | 2 | 6 | |
1 | 1 | 7 | |
1 | 1 | 5 | |
4 | 4 | 10 | |
1 | 1 | 4 | |
2 | 1 | 5 | |
1 | 1 | 7 | |
2 | 2 | 8 | |
3 | 1 | 6 |
optimal |
|||
3 | 1 | 4 | |
3 | 2 | 6 | |
1 | 1 | 7 | |
1 | 1 | 5 | |
4 | 4 | 10 | |
1 | 1 | 4 | |
2 | 1 | 5 | |
1 | 1 | 7 | |
2 | 2 | 8 | |
3 | 1 | 6 |
[1] |
Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082 |
[2] |
Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020171 |
[3] |
Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055 |
[4] |
Neil S. Trudinger, Xu-Jia Wang. Quasilinear elliptic equations with signed measure. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 477-494. doi: 10.3934/dcds.2009.23.477 |
[5] |
Masaharu Taniguchi. Axisymmetric traveling fronts in balanced bistable reaction-diffusion equations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3981-3995. doi: 10.3934/dcds.2020126 |
[6] |
Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Existence results and stability analysis for a nonlinear fractional boundary value problem on a circular ring with an attached edge : A study of fractional calculus on metric graph. Networks & Heterogeneous Media, 2021 doi: 10.3934/nhm.2021003 |
[7] |
Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020404 |
[8] |
Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, 2021, 14 (1) : 89-113. doi: 10.3934/krm.2020050 |
[9] |
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 |
[10] |
Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106 |
[11] |
Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020164 |
[12] |
Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021002 |
[13] |
Kengo Nakai, Yoshitaka Saiki. Machine-learning construction of a model for a macroscopic fluid variable using the delay-coordinate of a scalar observable. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1079-1092. doi: 10.3934/dcdss.2020352 |
[14] |
Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial & Management Optimization, 2021, 17 (2) : 669-686. doi: 10.3934/jimo.2019128 |
[15] |
Gheorghe Craciun, Jiaxin Jin, Casian Pantea, Adrian Tudorascu. Convergence to the complex balanced equilibrium for some chemical reaction-diffusion systems with boundary equilibria. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1305-1335. doi: 10.3934/dcdsb.2020164 |
[16] |
Peter Frolkovič, Karol Mikula, Jooyoung Hahn, Dirk Martin, Branislav Basara. Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 865-879. doi: 10.3934/dcdss.2020350 |
[17] |
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 |
[18] |
Harrison Bray. Ergodicity of Bowen–Margulis measure for the Benoist 3-manifolds. Journal of Modern Dynamics, 2020, 16: 305-329. doi: 10.3934/jmd.2020011 |
[19] |
Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217 |
[20] |
Giulia Luise, Giuseppe Savaré. Contraction and regularizing properties of heat flows in metric measure spaces. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 273-297. doi: 10.3934/dcdss.2020327 |
2019 Impact Factor: 1.366
Tools
Article outline
Figures and Tables
[Back to Top]