Title: An approximation algorithm for the 2-level uncapacitated facility location problem
Abstract: 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.
Publication Year: 2000
Publication Date: 2000-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot