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

A polynomial time approximation algorithm for the shifted two level MAX uncapacitated facility location problem (UFLP) problem was described. The problem was based on the technique of independently randomized rounding. The facilities in each level were opened and assigned each demand point to a path along open facilities such that the total profit was maximized when facilities were located on k levels. It was found that even if the facilities were opened independently, the events corresponding to paths being opened became dependent.