Improved Approximation Algorithms for the Uncapacitated Facility Location Problem

摘要: We consider the uncapacitated facility location problem. In this problem, there is a set of locations at which facilities can be built; fixed cost fi incurred if opened i. Furthermore, demand to serviced by facilities; j assigned i, then an associated service proportional distance between i and j, cij. The objective determine open assignment points facilities, so as minimize total cost. assume that function c symmetric satisfies triangle inequality. For problem we obtain (1+2/e)-approximation algorithm, where $1+2/e \approx 1.736$, significant improvement on previously known approximation guarantees. The algorithm works rounding optimal fractional solution linear programming relaxation. Our techniques use properties solutions program, randomized rounding, well generalization decomposition Shmoys, Tardos, Aardal [Proceedings 29th ACM Symposium Theory Computing, El Paso, TX, 1997, pp. 265--274].