An approximation algorithm for the 2-level uncapacitated facility location

A.F. Bumb

Research output: Book/ReportReportProfessional

14 Downloads (Pure)


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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages9
ISBN (Print)0169-2690
Publication statusPublished - 2000

Publication series

NameMemorandum / Faculty of Mathematical Sciences
PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


  • EWI-3360
  • MSC-90B80
  • IR-65727
  • MSC-68W25
  • METIS-141198
  • MSC-68W20

Cite this