2024/12/03 by Haitao Xu, Xu, Haitao, Jingru Zhang +1
Mathematics · #Fuzzy Systems and Optimization
paper · pdf · doi:10.48550/arxiv.2412.02580
In this paper, we consider the (weighted) two-center problem of uncertain points on a tree. Given are a tree T and a set \calP of n (weighted) uncertain points each of which has m possible locations on T associated with probabilities. The goal is to compute two points on T, i.e., two centers with respect to \calP, so that the maximum (weighted) expected distance of n uncertain points to their own expected closest center is minimized. This problem can be solved in O(|T|+ n2log nlog mn + mnlog2 mn log n) time by the algorithm for the general k-center problem. In this paper, we give a more efficient and simple algorithm that solves this problem in O(|T| + mnlog mn) time.