Vertex quickest 1-center location problem on trees and its inverse problem under weighted l∞ norm.

Autor: Qian, Xinqiang, Guan, Xiucui, Jia, Junhua, Zhang, Qiao, Pardalos, Panos M.
Předmět:
Zdroj: Journal of Global Optimization; Feb2023, Vol. 85 Issue 2, p461-485, 25p
Abstrakt: In view of some shortcomings of traditional vertex 1-center (V1C), we introduce a vertex quickest 1-center (VQ1C) problem on a tree, which aims to find a vertex such that the maximum transmission time to transmit σ units data is minimum. We first characterize some intrinsic properties of VQ1C and design a binary search algorithm in O (n log n) time based on the relationship between V1C and VQ1C, where n is the number of vertices. Furthermore, we investigate the inverse VQ1C problem under weighted l ∞ norm, in which we modify a given capacity vector in an optimal way such that a prespecified vertex becomes the vertex quickest 1-center. We introduce a concept of an effective modification and provide some optimality conditions for the problem. Then we propose an O (n 2 log n) time algorithm. Finally, we show some numerical experiments to verify the efficiency of the algorithms. [ABSTRACT FROM AUTHOR]
Databáze: Complementary Index
Externí odkaz: