Computing the Center of Uncertain Points on Cactus Graphs
| Autor: | Hu, Ran, Kanani, Divy H., Zhang, Jingru |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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| + mn\log mn)$-time algorithm for solving it. Since the input is $O(|G|+mn)$, our algorithm is almost optimal. Comment: A preliminary version of this paper appeared in Proceeding of the 34th International Workshop on Combinatorial Algorithms (IWOCA 2023) |
| Databáze: | arXiv |
| Externí odkaz: |
|