  The facility location problem is an NP-hard optimization problem. Therefore,
approximation algorithms are often used to solve large instances. Such
algorithms often perform much better than worst-case analysis suggests.
Therefore, probabilistic analysis is a widely used tool to analyze such
algorithms. Most research on probabilistic analysis of NP-hard optimization
problems involving metric spaces, such as the facility location problem, has
been focused on Euclidean instances, and also instances with independent
(random) edge lengths, which are non-metric, have been researched. We would
like to extend this knowledge to other, more general, metrics.
  We investigate the facility location problem using random shortest path
metrics. We analyze some probabilistic properties for a simple greedy heuristic
which gives a solution to the facility location problem: opening the $\kappa$
cheapest facilities (with $\kappa$ only depending on the facility opening
costs). If the facility opening costs are such that $\kappa$ is not too large,
then we show that this heuristic is asymptotically optimal. On the other hand,
for large values of $\kappa$, the analysis becomes more difficult, and we
provide a closed-form expression as upper bound for the expected approximation
ratio. In the special case where all facility opening costs are equal this
closed-form expression reduces to $O(\sqrt[4]{\ln(n)})$ or $O(1)$ or even
$1+o(1)$ if the opening costs are sufficiently small.
