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:maxS"1xS"2@?FxEC(S"1,S"2)=maxS"1xS"2@?FxE@?k@?Dmax(i,j)@?S"1xS"2c"i"j"k-@?i@?S"1f"i-@?j@?S"2e"j,where F,E are finite sets and c"i"j"k,f"i,e"j>=0 are real numbers. Denote by C^* the optimal value of the problem and by C"R=@?"k"@?"Dmin"("i","j")"@?"F"x"Ec"i"j"k-@?"i"@?"Ff"i-@?"j"@?"Ee"j. We present a polynomial time algorithm based on randomized rounding that finds a solution (S"1,S"2) such thatC(S"1,S"2)-C"R>=0.47(C^*-C"R).