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 条

[21] Approximating the two-level facility location problem via a quasi-greedy approach [J].

Zhang, Jiawei .

MATHEMATICAL PROGRAMMING, 2006, 108 (01) :159-176

[22] A multiexchange local search algorithm for the capacitated facility location problem [J].

Zhang, JW ;

Chen, B ;

Ye, YY .

MATHEMATICS OF OPERATIONS RESEARCH, 2005, 30 (02) :389-403

[23] A new approximation algorithm for the k-facility location problem [J].

Zhang, Peng .

THEORETICAL COMPUTER SCIENCE, 2007, 384 (01) :126-135

← 1 2 3 →