Approximation Algorithms for Probabilistic Graphs
arXiv:1807.01191
Abstract
We study the k-median and k-center problems in probabilistic graphs. We analyze the hardness of these problems, and propose several algorithms with improved approximation ratios compared with the existing proposals.