An approximation algorithm for the maximization version of the two level uncapacitated facility location problem

We consider the maximization version of the two level uncapacitated facility location problem, in the following formulation: [GRAPHICS] where F, E are finite sets and c(ijk), f(i), e(j) greater than or equal to 0 are real numbers. Denote by C* the optimal value of the problem and by C-R = Sigma(kis an element ofD) min((i,j)is an element ofFxE)c(ijk) - Sigma(iis an element ofF) f(i)- E-jis an element ofE e(j). We present a polynomial time algorithm based on randomized rounding that finds a solution (S-1,S-2) such that C(S-1,S-2)-C(R)greater than or equal to0.47(C*-C-R).