Inverse obnoxious \(p\)-median location problems on trees with edge length modifications under different norms. (English) Zbl 1426.90058
Summary: In this paper, we consider an inverse obnoxious \(p\)-median location problem with \(p \geq 2\) on trees in which the aim is to change the edge lengths at the minimum total cost so that a predetermined set of \(p\) vertices becomes an obnoxious \(p\)-median location. A novel combinatorial algorithm with \(\mathcal{O}(p^2 | V(T) |^2 \log^2 | V(T) |)\) time complexity is proposed for obtaining an optimal solution of the problem under the weighted Manhattan norm. Moreover, optimal solution algorithms with \(\mathcal{O}(p^2 | V(T) |)\) time complexity are developed for the problem under the weighted Chebyshev norm and the weighted bottleneck-type Hamming distance.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C27 | Combinatorial optimization |
| 90B80 | Discrete location and assignment |
Keywords:
obnoxious \(p\)-median location; combinatorial optimization; inverse optimization; time complexity; tree networksReferences:
| [1] | Afrashteh, E.; Alizadeh, B.; Baroughi, F., Optimal algorithms for selective variants of the classical and inverse median location problems on trees, Optim. Methods Softw. (2018) |
| [2] | Afrashteh, E.; Alizadeh, B.; Baroughi, F.; Nguyen, K. T., Linear time optimal approaches for max-profit inverse 1-median location problems, Asia-Pac. J. Oper. Res., Article 1850030 pp. (2018) · Zbl 1404.90088 |
| [3] | Alizadeh, B.; Afrashteh, E.; Baroughi, F., Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks, J. Optim. Theory Appl., 178, 914-934 (2018) · Zbl 1410.90115 |
| [4] | Alizadeh, B.; Bakhteh, S., A modified firefly algorithm for general inverse \(p\)-median location problems under different distance norms, Opsearch, 54, 618-636 (2017) · Zbl 1397.90406 |
| [5] | Alizadeh, B.; Burkard, R. E., Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58, 190-200 (2011) · Zbl 1236.90094 |
| [6] | Alizadeh, B.; Burkard, R. E., Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees, Discrete Appl. Math., 159, 706-716 (2011) · Zbl 1220.90104 |
| [7] | Alizadeh, B.; Burkard, R. E., A linear time algorithm for inverse obnoxious center location problems on networks, Cent. Eur. J. Oper. Res., 21, 585-594 (2013) · Zbl 1339.90188 |
| [8] | Alizadeh, B.; Burkard, R. E.; Pferschy, U., Inverse 1-center location problems with edge length augmentation on trees, Computing, 86, 331-343 (2009) · Zbl 1180.90163 |
| [9] | Alizadeh, B.; Etemad, R., Optimal algorithms for inverse vertex obnoxious center location problems on graphs, Theoret. Comput. Sci., 707, 36-45 (2018) · Zbl 1396.90092 |
| [10] | Baroughi Bonab, F.; Burkard, R. E.; Alizadeh, B., Inverse median location problems with variable coordinates, Cent. Eur. J. Oper. Res., 18, 365-381 (2010) · Zbl 1204.90059 |
| [11] | Baroughi Bonab, F.; Burkard, R. E.; Gassner, E., Inverse \(p\)-median problems with variable edge lengths, Math. Methods Oper. Res., 73, 263-280 (2011) · Zbl 1216.49032 |
| [12] | Burkard, R. E.; Fathali, J.; Kakhki, H. T., The \(p\)-maxian problem on a tree, Oper. Res. Lett., 35, 331-335 (2007) · Zbl 1180.90164 |
| [13] | Burkard, R. E.; Galavii, M.; Gassner, E., The inverse Fermat-Weber problem, European J. Oper. Res., 206, 11-17 (2010) · Zbl 1188.90209 |
| [14] | Burkard, R. E.; Pleschiutsching, C.; Zhang, J., Inverse median problems, Discrete Optim., 1, 23-39 (2004) · Zbl 1087.90038 |
| [15] | Burkard, R. E.; Pleschiutsching, C.; Zhang, J., The inverse 1-median problem on a cycle, Discrete Optim., 5, 242-253 (2008) · Zbl 1177.90245 |
| [16] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press: MIT Press Cambridge · Zbl 1047.68161 |
| [17] | Eiselt, H. A., Foundation of Location Analysis (2011), Springer: Springer New York · Zbl 1351.90007 |
| [18] | Farahani, R. Z.; Hekmatfar, M., Facility Location: Concepts, Models, Algorithms and Case Studies (2009), Physica Verlag: Physica Verlag Berlin |
| [19] | Galavii, M., The inverse 1-median problem on a tree and on a path, Electron. Notes Discrete Math., 36, 1241-1248 (2010) · Zbl 1274.90305 |
| [20] | Gassner, E., The inverse 1-maxian problem with edge length modification, J. Comb. Optim., 16, 50-67 (2008) · Zbl 1180.90165 |
| [21] | Guan, X. C.; Zhang, B. W., Inverse 1-median problem on trees under weighted Hamming distance, J. Global Optim., 54, 75-82 (2012) · Zbl 1273.90237 |
| [22] | Handler, G. Y., Minimax location of a facility in an undirected tree networks, Transp. Sci., 7, 287-293 (1973) |
| [23] | Hatzl, J., 2-Balanced flows and the inverse 1-median problem in the Chebyshev space, Discrete Optim., 9, 137-148 (2012) · Zbl 1254.90100 |
| [24] | Henzinger, M. R.; Klein, P. N.; Rao, S.; Subramanian, S., Faster shortest-path algorithms for planar graphs, J. Comput. System Sci., 55, 3-23 (1997) · Zbl 0880.68099 |
| [25] | Korte, B.; Vygen, J., Combinatorial Optimization: Theory and Algorithms (2012), Springer: Springer Berlin · Zbl 1237.90001 |
| [26] | Mirchandani, P. B.; Francis, R. L., Discrete Location Theory (1990), John Wiley: John Wiley New York · Zbl 0718.00021 |
| [27] | Nguyen, K. T., Inverse 1-median problem on block graphs with variable vertex weights, J. Optim. Theory Appl., 168, 944-957 (2016) · Zbl 1338.90085 |
| [28] | Nguyen, K. T.; Chi, N. T.L., A model for the inverse 1-median problem on trees under uncertain costs, Opuscula Math., 36, 513-523 (2016) · Zbl 1338.90086 |
| [29] | Nguyen, K. T.; Sepasian, A. R., The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, J. Comb. Optim., 32, 872-884 (2016) · Zbl 1354.90113 |
| [30] | Nguyen, K. T.; Vui, P. T., The inverse \(p\)-maxian problem on trees with variable edge lengths, Taiwanese J. Math., 20, 1437-1449 (2016) · Zbl 1357.90023 |
| [31] | Orlin, J. B., A faster strongly polynomial minimum cost flow algorithm, Oper. Res., 41, 338-350 (1993) · Zbl 0781.90036 |
| [32] | Sepasian, A. R.; Rahbarnia, F., An \(O(n \log n)\) algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions, Optimization, 64, 595-602 (2015) · Zbl 1308.90028 |
| [33] | Yang, X.; Zhang, J., Inverse center location problem on a tree, J. Syst. Sci. Complex., 21, 651-664 (2008) · Zbl 1180.90171 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
