On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem.

Abraham Flaxman, Alan M. Frieze, Juan Carlos Vera

Browse the full STOC paper archive.