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.
|Place of Publication||Enschede|
|Publisher||University of Twente, Department of Applied Mathematics|
|Number of pages||9|
|Publication status||Published - 2000|
|Name||Memorandum / Faculty of Mathematical Sciences|
|Publisher||Department of Applied Mathematics, University of Twente|
Bumb, A. F. (2000). An approximation algorithm for the 2-level uncapacitated facility location. (Memorandum / Faculty of Mathematical Sciences; No. 1540). Enschede: University of Twente, Department of Applied Mathematics.