Reverse 1-maxian problem with keeping existing 1-median. (English) Zbl 07044875
Summary: Here we investigate the reverse 1-maxian problem when it is necessary to keep 1-median of a given network. This problem asks to modify the parameters of the network so that the 1-median does not change and the candidate place for 1-maxian improves as much as possible. For the uniform-cost model on a tree graph, an algorithm with \(O(n \log n)\) time complexity is developed. It is also shown that the problem is solvable in linear time where it is only allowed to increase the vertex weights.
MSC:
| 90Bxx | Operations research and management science |
| 90C35 | Programming involving graphs or networks |
| 90C27 | Combinatorial optimization |
| 90C05 | Linear programming |
References:
| [1] | Krarup, J., Pisinger, D., Plastria, F.: Discrete location problems with push – pull objectives. Discrete Appl. Math. 123, 363-378 (2002) · Zbl 1012.90028 · doi:10.1016/S0166-218X(01)00346-8 |
| [2] | Berman, O., Ingco, D.I., Odoni, A.: Improving the location of minsum facilities through network modification. Ann. Oper. Res. 40, 1-16 (1992) · Zbl 0787.90035 · doi:10.1007/BF02060467 |
| [3] | Berman, O., Ingco, D.I., Odoni, A.R.: Improving the location of minmax facilities through network modification. Networks 24, 31-41 (1994) · Zbl 0799.90074 · doi:10.1002/net.3230240105 |
| [4] | Zhang, J.Z., Liu, Z.H., Ma, Z.F.: Some reverse location problems. Eur. J. Oper. Res. 124, 77-88 (2000) · Zbl 0960.90056 · doi:10.1016/S0377-2217(99)00122-8 |
| [5] | Nguyen, K.T.: reverse 1-center problem on weighted trees. Optimization 65(1), 253-264 (2016) · Zbl 1332.90052 · doi:10.1080/02331934.2014.994626 |
| [6] | Burkard, R.E., Gassner, E., Hatzl, J.: A linear time algorithm for the reverse 1-median problem on a cycle. Networks 48, 16-23 (2006) · Zbl 1103.90082 · doi:10.1002/net.20115 |
| [7] | Burkard, E.R., Gassner, E., Hatzl, J.: Reverse 2-median problem on trees. Discrete Appl. Math. 156, 1963-1976 (2008) · Zbl 1216.90072 · doi:10.1016/j.dam.2007.04.005 |
| [8] | Alizadeh, B., Etemad, R.: Linear time optimal approaches for reverse obnoxious center location problems on networks. Optimization 65(11), 2025-2036 (2016) · Zbl 1351.90111 · doi:10.1080/02331934.2016.1203915 |
| [9] | Etemad, R., Alizadeh, B.: Reverse selective obnoxious center location problems on tree graphs. Math. Methods Oper. Res. 87, 431-450 (2017). https://doi.org/10.1007/s00186-017-0624-y · Zbl 1391.90372 · doi:10.1007/s00186-017-0624-y |
| [10] | Etemad, R., Alizade, B.: Some variants of reverse selective center location problem on trees under the Chebyshev and Hamming norms. Yugosl. J. Oper. Res. 27(3), 367-384 (2016) · Zbl 1474.90375 · doi:10.2298/YJOR160317012E |
| [11] | Gassner, E.: The Inverse 1-maxian problem with edge length modification. J. Comb. Optim. 16(1), 50-67 (2008) · Zbl 1180.90165 · doi:10.1007/s10878-007-9098-9 |
| [12] | Burkard, R.E., Pleschiutschnig, C., Zhang, J.: Inverse median problems. Discrete Optim. 1, 23-39 (2004) · Zbl 1087.90038 · doi:10.1016/j.disopt.2004.03.003 |
| [13] | Burkard, R.E., Pleschiutschnig, C., Zhang, J.: Inverse median problem on a cycle. Discrete Optim. 5, 242-253 (2009) · Zbl 1177.90245 · doi:10.1016/j.disopt.2006.11.008 |
| [14] | Sepasian, A.R., Rahbarnia, F.: An \[O(n \log n)O\](nlogn) algorithm for the Inverse 1-median problem on trees with variable vertex weights and edge reductions. Optimization 64(3), 595-602 (2015) · Zbl 1308.90028 |
| [15] | Nguyen, KT: Inverse 1-median problem on block graphs with variable vertex weights. J. Optim. Theory Appl. 168(3), 944-957 (2016) · Zbl 1338.90085 · doi:10.1007/s10957-015-0829-2 |
| [16] | Alizadeh, B., Etemad, R.: Optimal algorithms for inverse vertex obnoxious center location problems on graphs. Theor. Comput. Sci. 707, 36-45 (2016) · Zbl 1396.90092 · doi:10.1016/j.tcs.2017.10.001 |
| [17] | 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(3), 872-884 (2016) · Zbl 1354.90113 · doi:10.1007/s10878-015-9907-5 |
| [18] | Goldman, A.J.: Optimal center location in simple networks. Transp. Sci. 2, 77-91 (1962) |
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.
