2024/12/03 by Ran Hu, Hu, Ran, Divy H. Kanani +3
Computer Science · #Data Management and Algorithms #Advanced Database Systems and Queries
paper · pdf · doi:10.48550/arxiv.2412.02828
In this paper, we consider the (weighted) one-center problem of uncertain points on a cactus graph. Given are a cactus graph G and a set of n uncertain points. Each uncertain point has m possible locations on G with probabilities and a non-negative weight. The (weighted) one-center problem aims to compute a point (the center) x^* on G to minimize the maximum (weighted) expected distance from x^* to all uncertain points. No previous algorithm is known for this problem. In this paper, we propose an O(|G| + mnlog mn)-time algorithm for solving it. Since the input is O(|G|+mn), our algorithm is almost optimal.