  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.
