An approximation algorithm for the 2-level uncapacitated facility location problem

We present an approximation algorithm for the maximization version of the two level uncapacitated facility location problem achieving a performance guarantee of $0.47.$ The main idea is to reduce the problem to a special case of MAX SAT, for which an approximation algorithm based on randomized rounding is presented.