Quick and good facility location
Mikkel Thorup · Symposium on Discrete Algorithms · 2003
We consider the facility location problem with shortest path distances in a weighted graph. W.h.p., we get an approximation factor of 1.62 in O(n + m) time with n and m the number of nodes and edges. Also, as a kind of warm-up, for a metric with a constant-times distance oracle, we get the factor 1.62 deterministically in O(n2 log n) time.Our results build on a recent facility location algorithm of Jain, Mahdian, and Saberi (STOC'02) achieving an approximation factor of 1.61 in O(n3) time.