×

Some variants of reverse selective center location problem on trees under the Chebyshev and Hamming norms. (English) Zbl 1474.90375

Summary: This paper is concerned with two variants of the reverse selective center location problems on tree graphs under the Hamming and Chebyshev cost norms in which the customers are existing on a selective subset of the vertices of the underlying tree. The first model aims to modify the edge lengths within a given modification budget until a prespecified facility location becomes as close as possible to the customer points. However, the other model wishes to change the edge lengths at the minimum total cost so that the distances between the prespecified facility and the customers satisfy a given upper bound. We develop novel combinatorial algorithms with polynomial time complexities for deriving the optimal solutions of the problems under investigation.

MSC:

90C27 Combinatorial optimization
90B80 Discrete location and assignment
90B85 Continuous location
90C35 Programming involving graphs or networks
Full Text: DOI

References:

[1] Alizadeh, B., and Burkard, R.E., “Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees”,Networks, 58 (2011) 190-200. · Zbl 1236.90094
[2] Alizadeh, B., and Burkard, R.E., “Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees”,Discrete Applied Mathematics, 159 (2011) 706-716. · Zbl 1220.90104
[3] Alizadeh, B., and Burkard, R.E., “A linear time algorithm for inverse obnoxious center location problems on networks”,Central European Journal of Operations Research, 21 (2012) 585-594. · Zbl 1339.90188
[4] Alizadeh, B., Burkard, R.E., and Pferschy, U., “Inverse 1-center location problems with edge length augmentation on trees”,Computing, 86 (2009) 331-343. · Zbl 1180.90163
[5] Alizadeh, B., and Etemad, R., “The linear time optimal approaches for reverse obnoxious center location problems on networks”,Optimization65 (11) (2016) 2025-2036. · Zbl 1351.90111
[6] Berman, O., Ingco, D.I., and Odoni, A.R., “Improving the location of minmax facility through network modification”,Networks, 24 (1994) 31-41. · Zbl 0799.90074
[7] Cai, M.C., Yang, X.G., and Zhang, JZ., “The complexity analysis of the inverese center location problem”,Journal of Global Optimization, 15 (1999) 213-218. · Zbl 0978.90065
[8] Eiselt, H.A.,Foundation of Location Analysis, Springer Verlag, New York, 2011.
[9] Korte, B., and Vygen, J.,Combinatorial Optimization, Theory and Algorithms, Springer Verlag, New York, 2011. · Zbl 1207.90002
[10] Mirchandani, P.B., and Francis, R.L.,Discrete Location Theory, John Wiley, New York, 1990. · Zbl 0718.00021
[11] Nguyen, K.T., and Chassein, A., “Inverse eccentric vertex problem on networks”,Central European Journal of Operations Research, 23 (2015) 687-698. · Zbl 1339.90286
[12] Nguyen, K.T., and Sepasian, A.R., “The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance”,Journal of Combinatorial Optimization, 32 (3) (2016) 872-884. · Zbl 1354.90113
[13] Nguyen, K.T., and Anh, L.Q., “Inversek-centrum problem on trees with variable vertex weights”, Mathematical Methods of Operations Research, 82 (2015) 19-30. · Zbl 1330.90120
[14] Nguyen, K.T., “Reverse 1-center problem on weighted trees”,Optimization, 65 (2015) 253-264. · Zbl 1332.90052
[15] Vygen, J., “On dual minimum cost flow algorithms”,Mathematical Methods of Operations Research, 56 (2002) 101-126. · Zbl 1023.90074
[16] Yang, X., and Zhang, J., “Inverse center location problem on a tree”,Journal of System Science and Complexity, 21 (2008) 651-664. · Zbl 1180.90171
[17] Zanjirani, R., and Hekmatfar, M.,Facility location: concepts, models, algorithms and case studies, Physica-Verlag, Berlin, 2009.
[18] Zhang, J.Z., Liu, Z.H., and Ma, Z.F., “Some reverse location problems”,European Journal of Operational Research, 124 (2000) 77-88. · Zbl 0960.90056
[19] Zhang, J.Z., Yang, X.G., and Cai, M.C., “A network improvement problem under different norms”,Computational Optimization and Applications, 27 (2004) 305-319. · Zbl 1061.90010
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.