Uncertain k-Center Clustering, Revisited: Point Assignment

We deal with optimization problems in many real-world scenarios that involve uncertain parameters and inputs. In this paper, we study the k-center problem for uncertain points. As in [1] we model the uncertain data as a set of probabilistic points, each of which is formalized as a probability distribution function that describes the possible locations of the points. We present real-world scenarios in which we need to find k centers that minimize the expected cost. In the assigned version of the uncertain k-center problem, we also compute the center of each uncertain point regardless of its realization. We focus on finding a proper assignment that give a smaller expected cost for the k-center compared to the known assignments. We define two new heuristic assignment rules, which we call ECA and OBA, implement our algorithms on real datasets, and compare the results with a recent state-of-the-art algorithm. Our experimental results show that OBA yields a significant improvement in the expected cost, whereas ECA yields an improvement in certain datasets.