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: maxS1×S2⊆F×E C(S1,S2) = maxS1×S2⊆F×E Σk∈D max(i,j)∈S1×S2 cijk − Σi∈S1 fi − Σj∈S2 ej, where F, E are finite sets and cijk, fi, ej ⩾ 0 are real numbers. Denote by C* the optimal value of the problem and by CR = Σk∈D min(i,j)∈F×E cijk − Σi∈F fi − Σj∈E ej. We present a polynomial time algorithm based on randomized rounding that finds a solution (S1,S2) such that C(S1,S2) − CR ⩾ 0.47(C* − CR).