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

被引：12

作者：

Wang, Zhen ^{[1
]}

Du, Donglei ^{[2
]}

Gabor, Adriana F. ^{[3
]}

Xu, Dachuan ^{[1
]}

机构：

[1] Beijing Univ Technol, Dept Appl Math, Beijing 100124, Peoples R China

[2] Univ New Brunswick, Fac Business Adm, Fredericton, NB E3B 5A3, Canada

[3] Erasmus Univ, Dept Econometr, Erasmus Sch Econ, NL-3000 DR Rotterdam, Netherlands

来源：

OPERATIONS RESEARCH LETTERS | 2010年 / 38卷 / 05期

基金：

北京市自然科学基金; 加拿大自然科学与工程研究理事会;

关键词：

Facility location; Approximation algorithm; Randomized rounding;

D O I：

10.1016/j.orl.2010.04.010

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：386 / 389

页数：4

共 23 条

[1] A 3-approximation algorithm for the k-level uncapacitated facility location problem [J].

Aardal, K ;

Chudak, FA ;

Shmoys, DB .

INFORMATION PROCESSING LETTERS, 1999, 72 (5-6) :161-167

[2] Improved combinatorial approximation algorithms for the k-level facility location problem [J].

Ageev, A ;

Ye, YY ;

Zhang, JW .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 18 (01) :207-217

[3]

Bumb A, 2001, LECT NOTES COMPUT SC, V2129, P55

[4] AN OPTIMAL BIFACTOR APPROXIMATION ALGORITHM FOR THE METRIC UNCAPACITATED FACILITY LOCATION PROBLEM [J].

Byrka, Jaroslaw ;

Aardal, Karen .

SIAM JOURNAL ON COMPUTING, 2010, 39 (06) :2212-2231

[5] Supporting multiple-input, multiple-output custom functions in configurable processors [J].

Chen, Xiaoyong ;

Maskell, Douglas L. .

JOURNAL OF SYSTEMS ARCHITECTURE, 2007, 53 (5-6) :263-271

[6] Improved approximation algorithms for the uncapacitated facility location problem [J].

Chudak, FA ;

Shmoys, DB .

SIAM JOURNAL ON COMPUTING, 2003, 33 (01) :1-25

[7] A new approximation algorithm for the multilevel facility location problem [J].

Gabor, Adriana F. ;

van Ommeren, Jan-Kees C. W. .

DISCRETE APPLIED MATHEMATICS, 2010, 158 (05) :453-460

[8] Greedy strikes back: Improved facility location algorithms [J].

Guha, S ;

Khuller, S .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 31 (01) :228-248

[9] Greedy facility location algorithms analyzed using,dual fitting with factor-revealing LP [J].

Jain, K ;

Mahdian, M ;

Markakis, E ;

Saberi, A ;

Vazirani, VV .

JOURNAL OF THE ACM, 2003, 50 (06) :795-824

[10] Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J].

Jain, K ;

Vazirani, VV .

JOURNAL OF THE ACM, 2001, 48 (02) :274-296

← 1 2 3 →