Some variants of reverse selective center location problem on trees under the Chebyshev and Hamming norms
DOI:
https://doi.org/10.2298/YJOR160317012EKeywords:
center location problems, combinatorial optimization, reverse optimization, tree graphs, time complexityAbstract
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.References
Alizadeh, B., and Burkard, R.E., “Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees”, Networks, 58 (2011) 190–200.
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.
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.
Alizadeh, B., Burkard, R.E., and Pferschy, U., “Inverse 1-center location problems with edge length augmentation on trees”, Computing, 86 (2009) 331–343.
Alizadeh, B., and Etemad, R., “The linear time optimal approaches for reverse obnoxious center location problems on networks”, Optimization, 65 (11) (2016) 2025–2036.
Berman, O., Ingco, D.I., and Odoni, A.R., “Improving the location of minmax facility through network modification”, Networks, 24 (1994) 31–41.
Cai, M.C., Yang, X.G., and Zhang, J.Z., “The complexity analysis of the inverse center location problem”, Journal of Global Optimization, 15 (1999) 213–218.
Eiselt, H.A., Foundation of Location Analysis, Springer Verlag, New York, 2011.
Korte, B., and Vygen, J., Combinatorial Optimization, Theory and Algorithms, Springer Verlag, New York, 2011.
Mirchandani, P.B., and Francis, R.L., Discrete Location Theory, John Wiley, New York, 1990.
Nguyen, K.T., and Chassein, A., “Inverse eccentric vertex problem on networks”, Central European Journal of Operations Research, 23 (2015) 687–698.
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.
Nguyen, K.T., and Anh, L.Q., “Inverse k-centrum problem on trees with variable vertex weights”, Mathematical Methods of Operations Research, 82 (2015) 19–30.
Nguyen, K.T., “Reverse 1-center problem on weighted trees”, Optimization, 65 (2015) 253–264.
Vygen, J., “On dual minimum cost flow algorithms”, Mathematical Methods of Operations Research, 56 (2002) 101–126.
Yang, X., and Zhang, J., “Inverse center location problem on a tree”, Journal of System Science and Complexity, 21 (2008) 651–664.
Zanjirani, R., and Hekmatfar, M., Facility Location: Concepts, Models, Algorithms and Case Studies, Physica-Verlag, Berlin, 2009.
Zhang, J.Z., Liu, Z.H., and Ma, Z.F., “Some reverse location problems”, European Journal of Operational Research, 124 (2000) 77–88.
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.
Downloads
Published
Issue
Section
License
Copyright (c) 2017 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
