An approximation algorithm for the 2-level uncapacitated facility location

A.F. Bumb

Research output: Book/ReportReportProfessional

12 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.
Bumb, A.F. / An approximation algorithm for the 2-level uncapacitated facility location. Enschede : University of Twente, Department of Applied Mathematics, 2000. 9 p. (Memorandum / Faculty of Mathematical Sciences; 1540).
@book{6d273484e0b440e880364df5d16db06d,
title = "An approximation algorithm for the 2-level uncapacitated facility location",
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.",
keywords = "EWI-3360, MSC-90B80, IR-65727, MSC-68W25, METIS-141198, MSC-68W20",
author = "A.F. Bumb",
note = "Imported from MEMORANDA",
year = "2000",
language = "Undefined",
isbn = "0169-2690",
series = "Memorandum / Faculty of Mathematical Sciences",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1540",

}

Bumb, AF 2000, An approximation algorithm for the 2-level uncapacitated facility location. Memorandum / Faculty of Mathematical Sciences, no. 1540, University of Twente, Department of Applied Mathematics, Enschede.

An approximation algorithm for the 2-level uncapacitated facility location. / Bumb, A.F.

Enschede : University of Twente, Department of Applied Mathematics, 2000. 9 p. (Memorandum / Faculty of Mathematical Sciences; No. 1540).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - An approximation algorithm for the 2-level uncapacitated facility location

AU - Bumb, A.F.

N1 - Imported from MEMORANDA

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

KW - EWI-3360

KW - MSC-90B80

KW - IR-65727

KW - MSC-68W25

KW - METIS-141198

KW - MSC-68W20

M3 - Report

SN - 0169-2690

T3 - Memorandum / Faculty of Mathematical Sciences

BT - An approximation algorithm for the 2-level uncapacitated facility location

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Bumb AF. An approximation algorithm for the 2-level uncapacitated facility location. Enschede: University of Twente, Department of Applied Mathematics, 2000. 9 p. (Memorandum / Faculty of Mathematical Sciences; 1540).