Abstract
Given an undirected tree \(T=(V,E)\) and a value \(\sigma >0\), every edge \(e\in E\) has a lead time l(e) and a capacity c(e). Let \(P_{st}\) be the unique path connecting s and t. A transmission time of sending \(\sigma \) units data from s to \(t\in V\) is \(Q(s,t,\sigma )=l(P_{st})+\frac{\sigma }{c(P_{st})}\), where \(l(P_{st})=\sum _{e\in P_{st}}l(e)\) and \(c(P_{st})=\min _{e\in P_{st}} c(e)\). A vertex (an absolute) quickest 1-center problem is to determine a vertex \(s^*\in V\) (a point \(s^*\in T\), which is either a vertex or an interior point in some edge) whose maximum transmission time is minimum. In an inverse vertex (absolute) quickest 1-center problem on a tree T, we aim to modify a capacity vector with minimum cost under weighted \(l_1\) norm such that a given vertex (point) becomes a vertex (an absolute) quickest 1-center. We first introduce a maximum transmission time balance problem between two trees \(T_1\) and \(T_2\), where we reduce the maximum transmission time of \(T_1\) and increase the maximum transmission time of \(T_2\) until the maximum transmission time of the two trees become equal. We present an analytical form of the objective function of the problem and then design an \(O(n_1^2n_2)\) algorithm, where \(n_i\) is the number of vertices of \(T_i\) with \(i=1, 2\). Furthermore, we analyze some optimality conditions of the two inverse problems, which support us to transform them into corresponding maximum transmission time balance problems. Finally, we propose two \(O(n^3)\) algorithms, where n is the number of vertices in T.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alizadeh, B., Burkard, R.E.: Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees. Networks 58, 190–200 (2011)
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 (2012)
Burkard, R.E., Pleschiutschnig, C., Zhang, J.Z.: Inverse median problems. Discret. Optim. 1, 23–39 (2004)
Cai, M.C., Yang, X.G., Zhang, J.Z.: The complexity analysis of the inverse center location problem. J. Glob. Optim. 15, 213–218 (1999)
Chen, Y.L., Chin, Y.H.: The quickest path problem. Comput. Oper. Res. 17, 153–161 (1990)
Daskin, M.S.: Network and discrete location: models, algorithms, and applications. Wiley, Hoboken (2011)
Garrett, S.J.: Introductory numerical methods. In: Introduction to Actuarial and Financial Mathematical Methods. Academic. Press. pp. 411–463 (2015)
Gassner, E.: The inverse 1-maxian problem with edge length modification. J. Comb. Optim. 16, 50–67 (2008)
Ghiyasvand, M., Keshtkar, I.: Solving the absolute 1-center problem in the quickest path case. Bull. Iran. Math. Soc. 48, 643–671 (2022)
Guan, X.C., Zhang, B.W.: Inverse 1-median problem on trees under weighted Hamming distance. J. Glob. Optim. 54(1), 75–82 (2012)
Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res. 12(3), 450–459 (1964)
Handler, G.Y.: Minimax location of a facility in an undirected tree graph. Transp. Sci. 7(3), 287–293 (1973)
Hasanzadeh, B., Alizadeh, B., Baroughi, F.: Optimal algorithms for inverse obnoxious center location problems under the weighted Chebyshev and Hamming cost norms on networks. Optimization (2022). https://doi.org/10.1080/02331934
Keshtkar, I., Ghiyasvand, M.: Inverse quickest center location problem on a tree. Discret. Appl. Math. 260, 188–202 (2019)
Martins, E.Q.V., Santos, J.L.E.: An algorithm for the quickest path problem. Oper. Res. Lett. 20, 195–198 (1997)
Mohammadi, S., Alizadeh, B., Baroughi, F., Afrashteh, E.: A modified directional bat algorithm for extensive inverse p-facility maxian location problems on networks. Soft. Comput. 26, 1941–1959 (2022)
Nguyen, K.T.: Inverse 1-median problem on block graphs with variable vertex weights. J. Optim. Theory Appl. 168, 944–957 (2016)
Nguyen, K.T., Chassein, A.: The inverse convex ordered 1-median problem on trees under Chebyshev norm and Hamming distance. Eur. J. Oper. Res. 247(3), 774–781 (2015)
Nguyen, K.T., Hung, N.T., Nguyen-Thu, H., Le, T.T., Pham, V.H.: On some inverse 1-center location problems. Optimization 68(5), 999–1015 (2019)
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)
Qian, X.Q., Guan, X.C., Jia, J.H., Zhang, Q., Pardalos, P.M.: Vertex quickest 1-center location problem on trees and its inverse problem under weighted \(l_\infty \) norm. J. Glob. Optim. 85, 461–485 (2023)
Qian, X.Q., Guan, X.C., Jia, J.H., Zhang, Q., Pardalos, P.M.: The absolute quickest 1-center location problem on trees and its inverse problem under weighted \(l_{\infty }\) norm. Submitted to Optimization. (2022)
Soltanpour, A., Baroughi, F., Alizadeh, B.: The inverse 1-median location problem on uncertain tree networks with tail value at risk criterion. Inform. Sci. 506, 383–394 (2020)
Tayyebi, J., Sepasian, A.R.: Reverse 1-centre problem on trees under convex piecewise-linear cost function. Optimization 72(3), 843–860 (2021)
Yang, X.G., Zhang, J.Z.: Inverse center location problem on a tree. J. Syst. Sci. Complex 21(4), 651–664 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Anita Schöbel.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Research is supported by National Natural Science Foundation of China (11471073).
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Qian, X., Guan, X., Jia, J. et al. Inverse Vertex/Absolute Quickest 1-Center Location Problem on a Tree Under Weighted \(l_1\) Norm. J Optim Theory Appl 200, 524–554 (2024). https://doi.org/10.1007/s10957-023-02362-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-023-02362-6