An Approximation Algorithm for the Stochastic Fault-Tolerant Facility Location Problem

被引：6

作者：

Wu C. ^{[1
]}

Xu D. ^{[2
]}

Shu J. ^{[3
]}

机构：

[1] School of Mathematical Sciences, Nankai University, Tianjing

[2] Department of Applied Mathematics, Beijing University of Technology, Beijing, 100124, 100 Pingleyuan, Chaoyang District

[3] Department of Management Science and Engineering, School of Economics and Management, Southeast University, Nanjing

来源：

Journal of the Operations Research Society of China | 2013年 / 1卷 / 04期

基金：

中国国家自然科学基金;

关键词：

Approximation algorithm; Facility location problem; LP rounding;

D O I：

10.1007/s40305-013-0034-7

中图分类号：

学科分类号：

摘要：

In this paper, we study a stochastic version of the fault-tolerant facility location problem. By exploiting the stochastic structure, we propose a 5-approximation algorithm which uses the LP-rounding technique based on the revised optimal solution to the linear programming relaxation of the stochastic fault-tolerant facility location problem. © 2013 Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg.

引用

页码：511 / 522

页数：11

共 23 条

[1]

Ageev A., Ye Y., Zhang J., Improved combinatorial approximation algorithms for the k-level facility location problem, SIAM J. Discrete Math., 18, pp. 207-217, (2004)

[2]

Byrka J., Aardal K.I., An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM J. Comput., 39, pp. 2212-2213, (2010)

[3]

Bykra J., Srinivasan A., Swamy C., Fault-tolerant facility location: a randomized dependent LP-rounding algorithm, Proc. Of IPCO, pp. 244-257, (2010)

[4]

Chen X., Chen B., Approximation algorithms for soft-capacitated facility location in capacitated network design, Algorithmica, 53, pp. 263-297, (2007)

[5]

Chudak F.A., Shmoys D.B., Improved approximation algorithms for the uncapacitated facility location problem, SIAM J. Comput., 33, pp. 1-25, (2003)

[6]

Guha S., Khuller S., Greedy strike back: improved facility location algorithms, J. Algorithms, 31, pp. 228-248, (1999)

[7]

Guha S., Meyerson A., Munagala K., A constant factor approximation algorithm for the fault-tolerant facility location problem, J. Algorithms, 48, pp. 429-440, (2003)

[8]

Jain K., Mahdian M., Markakis E., Saberi A., Vazirani V.V., Greedy facility location algorithm analyzed using dual fitting with factor-revealing LP, J. ACM, 50, pp. 795-824, (2003)

[9]

Jain K., Vazirani V.V., Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, J. ACM, 48, pp. 274-296, (2001)

[10]

Jain K., Vazirani V.V., Approximation algorithms for fault tolerant metric facility location problem, Algorithmica, 38, pp. 433-439, (2003)

← 1 2 3 →