The uncapacitated facility location problem in the following formulation is considered: maxS⊆I Z(S) = ∑j∈J maxi∈S bij − ∑i∈S ci, where I and j are finite sets, and bij, ci ⩾ 0 are rational numbers. Let Z* denote the optimal value of the problem and let ZR = ∑j∈J mini∈I bij − ∑i∈I ci. Cornuejols et al. prove that for the problem with the additional cardinality constraint | S | ⩽ K, a simple greedy algorithm finds a feasible solution S such that (Z(S) − ZR)/(Z* − ZR) ⩾ 1 − e−1 ≈ 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. It is proved that the algorithm delivers a solution S such that (Z(S) − ZR)/(Z* − ZR) ⩾ 2(√(2) − 1) ≈ 0.828. We also show that there exists ϵ > 0 such that it is NP-hard to find an approximate solution S with (Z(S) − ZR)/(Z* − ZR) ⩾ 1 − ϵ.
