Quick and good facility location

摘要

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(n² 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(n³) time.