An 0.828-approximation algorithm for the uncapacitated facility location problem

The uncapacitated facility location problem in the following formulation is considered: max(S subset of or equal to I) Z(S) = Sigma(j is an element of J)max(i is an element of S)b(ij) - Sigma(i is an element of S)c(i), where I and J are finite sets, and b(ij), c(i)greater than or equal to 0 are rational numbers. Let Z* denote the optimal value of the problem and let Z(R) = Sigma(j is an element of J)min(i is an element of I)b(ij) - Sigma(i is an element of I)c(i). Cornuejols et al. (Ann. Discrete Math. 1 (1977) 163-178) prove that for the problem with the additional cardinality constraint \S\less than or equal to K, a simple greedy algorithm finds a feasible solution S such that (Z(S) - ZR)/(Z* - ZR)greater than or equal to 1 - e(-1) approximate to 0.632. We suggest a polynomial-time approximation algorithm for the unconstrained version of the problem, based on the idea of randomized rounding due to Goemans and Williamson (SIAM J. Discrete Math. 7 (1994) 656 - 666). It is proved that the algorithm delivers a solution S such that (Z(S) - Z(R))/(Z* - Z(R))greater than or equal to 2(root 2 - 1) approximate to 0.828. We also show that there exists epsilon > 0 such that it is NP-hard to find an approximate solution S with (Z(S) - Z(R))/(Z* - Z(R))greater than or equal to 1 - epsilon. (C) 1999 Elsevier Science B.V. All rights reserved.