Inverse vertex/absolute quickest 1-center location problem on a tree under weighted \(l_1\) norm. (English) Zbl 1536.90191
Summary: 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^2 n_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\).
MSC:
| 90C27 | Combinatorial optimization |
References:
| [1] | Alizadeh, B.; Burkard, RE, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58, 190-200 (2011) · Zbl 1236.90094 · doi:10.1002/net.20427 |
| [2] | Alizadeh, B.; Burkard, RE, A linear time algorithm for inverse obnoxious center location problems on networks, Cent. Eur. J. Oper. Res., 21, 585-594 (2012) · Zbl 1339.90188 · doi:10.1007/s10100-012-0248-5 |
| [3] | Burkard, RE; Pleschiutschnig, C.; Zhang, JZ, Inverse median problems, Discret. Optim., 1, 23-39 (2004) · Zbl 1087.90038 · doi:10.1016/j.disopt.2004.03.003 |
| [4] | Cai, MC; Yang, XG; Zhang, JZ, The complexity analysis of the inverse center location problem, J. Glob. Optim., 15, 213-218 (1999) · Zbl 0978.90065 · doi:10.1023/A:1008360312607 |
| [5] | Chen, YL; Chin, YH, The quickest path problem, Comput. Oper. Res., 17, 153-161 (1990) · Zbl 0698.90083 · doi:10.1016/0305-0548(90)90039-A |
| [6] | Daskin, MS, Network and discrete location: models, algorithms, and applications (2011), Hoboken: Wiley, Hoboken |
| [7] | Garrett, S.J.: Introductory numerical methods. In: Introduction to Actuarial and Financial Mathematical Methods. Academic. Press. pp. 411-463 (2015) · Zbl 1319.91002 |
| [8] | Gassner, E., The inverse 1-maxian problem with edge length modification, J. Comb. Optim., 16, 50-67 (2008) · Zbl 1180.90165 · doi:10.1007/s10878-007-9098-9 |
| [9] | Ghiyasvand, M.; Keshtkar, I., Solving the absolute 1-center problem in the quickest path case, Bull. Iran. Math. Soc., 48, 643-671 (2022) · Zbl 1484.90093 · doi:10.1007/s41980-021-00536-4 |
| [10] | Guan, XC; Zhang, BW, Inverse 1-median problem on trees under weighted Hamming distance, J. Glob. Optim., 54, 1, 75-82 (2012) · Zbl 1273.90237 · doi:10.1007/s10898-011-9742-x |
| [11] | Hakimi, SL, Optimum locations of switching centers and the absolute centers and medians of a graph, Oper. Res., 12, 3, 450-459 (1964) · Zbl 0123.00305 · doi:10.1287/opre.12.3.450 |
| [12] | Handler, GY, Minimax location of a facility in an undirected tree graph, Transp. Sci., 7, 3, 287-293 (1973) · doi:10.1287/trsc.7.3.287 |
| [13] | 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) · doi:10.1080/02331934 |
| [14] | Keshtkar, I.; Ghiyasvand, M., Inverse quickest center location problem on a tree, Discret. Appl. Math., 260, 188-202 (2019) · Zbl 1409.05056 · doi:10.1016/j.dam.2019.01.001 |
| [15] | Martins, EQV; Santos, JLE, An algorithm for the quickest path problem, Oper. Res. Lett., 20, 195-198 (1997) · Zbl 0881.90124 · doi:10.1016/S0167-6377(97)00008-4 |
| [16] | 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) · doi:10.1007/s00500-021-06463-0 |
| [17] | Nguyen, KT, Inverse 1-median problem on block graphs with variable vertex weights, J. Optim. Theory Appl., 168, 944-957 (2016) · Zbl 1338.90085 · doi:10.1007/s10957-015-0829-2 |
| [18] | Nguyen, KT; 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) · Zbl 1346.90712 · doi:10.1016/j.ejor.2015.06.064 |
| [19] | Nguyen, KT; Hung, NT; Nguyen-Thu, H.; Le, TT; Pham, VH, On some inverse 1-center location problems, Optimization, 68, 5, 999-1015 (2019) · Zbl 1415.90015 · doi:10.1080/02331934.2019.1571056 |
| [20] | Nguyen, KT; Sepasian, AR, 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 |
| [21] | Qian, XQ; Guan, XC; Jia, JH; Zhang, Q.; Pardalos, PM, Vertex quickest 1-center location problem on trees and its inverse problem under weighted \(l_\infty\) norm, J. Glob. Optim., 85, 461-485 (2023) · Zbl 1512.90238 · doi:10.1007/s10898-022-01212-5 |
| [22] | 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) |
| [23] | 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) · Zbl 1456.90169 · doi:10.1016/j.ins.2019.08.018 |
| [24] | Tayyebi, J.; Sepasian, AR, Reverse 1-centre problem on trees under convex piecewise-linear cost function, Optimization, 72, 3, 843-860 (2021) · Zbl 1515.90145 · doi:10.1080/02331934.2021.1995730 |
| [25] | Yang, XG; Zhang, JZ, Inverse center location problem on a tree, J. Syst. Sci. Complex, 21, 4, 651-664 (2008) · Zbl 1180.90171 · doi:10.1007/s11424-008-9142-6 |
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.
