The k-Center Problem of Uncertain Points on Graphs

2025/04/21 by Xu, Haitao, Zhang, Jingru
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2504.14803

Abstract

In this paper, we study the k-center problem of uncertain points on a graph. Given are an undirected graph G = (V, E) and a set P of n uncertain points where each uncertain point with a non-negative weight has m possible locations on G each associated with a probability. The problem aims to find k centers (points) on G so as to minimize the maximum weighted expected distance of uncertain points to their expected closest centers. No previous work exist for the k-center problem of uncertain points on undirected graphs. We propose exact algorithms that solve respectively the case of k=2 in O(|E|²m²nlog |E|mnlog mn ) time and the problem with k≥ 3 in O(min\|E|^km^kn^k+1klog |E|mnlog m, |E|^kn^(k)/(2)m^(k²)/(2)log |E|mn\) time, provided with the distance matrix of G. In addition, an O(|E|mnlog mn)-time algorithmic approach is given for the one-center case.

Related

• The Two-Center Problem of Uncertain Points on Trees
• Computing the Center of Uncertain Points on Cactus Graphs
• The Two-Center Problem of Uncertain Points on Cactus Graphs
• Improved constant approximation factor algorithms for k-center problem for uncertain data
• Computing the Rectilinear Center of Uncertain Points in the Plane