An approximation algorithm for the κ-level stochastic facility location problem

Zhen Wang; Donglei Du; Adriana F. Gabor; Dachuan Xu

doi:10.1016/j.orl.2010.04.010

An approximation algorithm for the κ-level stochastic facility location problem

Zhen Wang
, Donglei Du
, Adriana F. Gabor
, Dachuan Xu

Mathematics

Beijing Polytechnic Univ
University of New Brunswick

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

We consider the k-level stochastic facility location problem. For this, we present an LP rounding algorithm that is 3-approximate. This result is achieved by a novel integer linear programming formulation that exploits the stochastic structure.

Original language	British English
Pages (from-to)	386-389
Number of pages	4
Journal	Operations Research Letters
Volume	38
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2010.04.010
State	Published - Sep 2010

Keywords

Approximation algorithm
Facility location
Randomized rounding

Access to Document

10.1016/j.orl.2010.04.010

OpenUrl availability

Full text

Cite this

@article{7cfe2e436e9f431ea1040d68b5223284,

title = "An approximation algorithm for the κ-level stochastic facility location problem",

abstract = "We consider the k-level stochastic facility location problem. For this, we present an LP rounding algorithm that is 3-approximate. This result is achieved by a novel integer linear programming formulation that exploits the stochastic structure.",

keywords = "Approximation algorithm, Facility location, Randomized rounding",

author = "Zhen Wang and Donglei Du and Gabor, \{Adriana F.\} and Dachuan Xu",

note = "Funding Information: The authors are grateful to Qin Wang and the area editor, both of whom offered insightful suggestions for improving the paper. The research of the first author is supported by Beijing Natural Science Foundation (No. 1102001 ). The second author{\textquoteright}s research is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant 283103 . The fourth author{\textquoteright}s research is supported by NSF of China (No. 60773185 ) and PHR (IHLB) .",

year = "2010",

month = sep,

doi = "10.1016/j.orl.2010.04.010",

language = "British English",

volume = "38",

pages = "386--389",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - An approximation algorithm for the κ-level stochastic facility location problem

AU - Wang, Zhen

AU - Du, Donglei

AU - Gabor, Adriana F.

AU - Xu, Dachuan

N1 - Funding Information: The authors are grateful to Qin Wang and the area editor, both of whom offered insightful suggestions for improving the paper. The research of the first author is supported by Beijing Natural Science Foundation (No. 1102001 ). The second author’s research is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) grant 283103 . The fourth author’s research is supported by NSF of China (No. 60773185 ) and PHR (IHLB) .

PY - 2010/9

Y1 - 2010/9

N2 - We consider the k-level stochastic facility location problem. For this, we present an LP rounding algorithm that is 3-approximate. This result is achieved by a novel integer linear programming formulation that exploits the stochastic structure.

AB - We consider the k-level stochastic facility location problem. For this, we present an LP rounding algorithm that is 3-approximate. This result is achieved by a novel integer linear programming formulation that exploits the stochastic structure.

KW - Approximation algorithm

KW - Facility location

KW - Randomized rounding

UR - https://www.scopus.com/pages/publications/77956340738

U2 - 10.1016/j.orl.2010.04.010

DO - 10.1016/j.orl.2010.04.010

M3 - Article

AN - SCOPUS:77956340738

SN - 0167-6377

VL - 38

SP - 386

EP - 389

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

An approximation algorithm for the κ-level stochastic facility location problem

Abstract

Keywords

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Cite this