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

共 50 条

[1] An Approximation Algorithm For The Stochastic Fault-tolerant Facility Location Problem
Wu, Chen-Chen
Xu, Da-Chuan
Shu, Jia
OPERATIONS RESEARCH AND ITS APPLICATIONS: IN ENGINEERING, TECHNOLOGY AND MANAGEMENT, 2011, 14 : 164 - +
[2] APPROXIMATION ALGORITHM FOR TWO-STAGE STOCHASTIC FAULT-TOLERANT FACILITY LOCATION PROBLEM
Zhang, Li
Li, Qiaoliang
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2025, 21 (03) : 1735 - 1748
[3] A constant factor approximation algorithm for the fault-tolerant facility location problem
Guha, S
Meyerson, A
Munagala, K
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2003, 48 (02): : 429 - 440
[4] Approximation algorithms for the fault-tolerant facility location problem with penalties
Ji, Sai
Xu, Dachuan
Du, Donglei
Wu, Chenchen
DISCRETE APPLIED MATHEMATICS, 2019, 264 : 62 - 75
[5] Approximation algorithms for the fault-tolerant facility location problem with submodular penalties
Yingying Guo
Qiaoliang Li
Journal of Combinatorial Optimization, 2024, 47
[6] Approximation algorithms for the fault-tolerant facility location problem with submodular penalties
Guo, Yingying
Li, Qiaoliang
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 47 (02)
[7] LP-rounding approximation algorithms for two-stage stochastic fault-tolerant facility location problem
Ji, Sai
Xu, Dachuan
Du, Donglei
Wang, Yijing
APPLIED MATHEMATICAL MODELLING, 2018, 58 : 76 - 85
[8] Improved approximation algorithms for the robust fault-tolerant facility location problem
Li, Yu
Xu, Dachuan
Du, Donglei
Xiu, Naihua
INFORMATION PROCESSING LETTERS, 2012, 112 (10) : 361 - 364
[9] Improved Approximation Algorithm for the Fault-Tolerant Facility Placement Problem with Rejection
Yu S.
American Journal of Mathematical and Management Sciences, 2020, 39 (02) : 122 - 128
[10] Fault-tolerant concave facility location problem with uniform requirements
Xing Wang
Da-Chuan Xu
Zheng-Hai Huang
Acta Mathematicae Applicatae Sinica, English Series, 2012, 28 : 475 - 484

← 1 2 3 4 5 →