Inverse Vertex/Absolute Quickest 1-Center Location Problem on a Tree Under Weighted l1 Norm

Journal of Optimization Theory and Applications. 2024. Vol. 200. P. 524–554.

Qian X., Guan X., Jia J., Pardalos P. M.

Given an undirected tree T = (V, E) and a value σ > 0, every edge e ∈ E has a lead time l(e) and a capacity c(e). Let Pst be the unique path connecting s and t. A transmission time of sending σ units data from s to t ∈ V is Q(s, t,σ) = l(Pst) + σ c(Pst), where l(Pst) = e∈Pst l(e) and c(Pst) = mine∈Pst c(e). A vertex (an absolute) quickest 1-center problem is to determine a vertex s∗ ∈ V (a point s∗ ∈ 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 l1 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 T1 and T2, where we reduce the maximum transmission time of T1 and increase the maximum transmission time of T2 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(n2 1n2) algorithm, where ni is the number of vertices of Ti 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(n3) algorithms, where n is the number of vertices in T .

Keywords: Inverse optimization problem, Tree, l1 norm, Center location, Quickest 1-center problem

Publication based on the results of: Network models, optimization and computational complexity (2024)