An approximation algorithm for the 2-level uncapacitated facility location

A.F. Bumb

Research output: Book/ReportReportProfessional

14 Downloads (Pure)

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.
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
No.1540
ISSN (Print)0169-2690

Keywords

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

Cite this

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.