随机容错设施布局问题的近似算法

Abstract

Abstract: In the deterministic fault-tolerant facility placement problem (FTFP), we are given a set of locations and a set of clients. We can open any number of different facilities with the same opening cost at each location. Each client j has an integer requirement r_j. Connecting client j to different facilities at the same location is permitted. The objective is to open some facilities and connect each client j to r_j different facilities such that the total cost is minimized. In this paper, we consider the two-stage stochastic fault-tolerant facility placement problem (SFTFP) with recourse in which the set of clients are unknown in advance. But there are finite scenarios materialized by a probability distribution. Each scenario specifies a subset of clients to be assigned. Moreover, each facility has two kinds of opening cost. In the first stage, we open a subset of facilities according to the stochastic information of the clients. In the second stage, we can open additional number of facilities when the actual information of the clients is revealed. We give a linear integral program and an LP-rounding based 5-approximation algorithm for the SFTFP.

Key words: facility placement problem, approximation algorithm, LP-rounding

SHAO Jia-Ting, Xu-Da-Chuan. An Approximation Agorithm for the Stochastic Fault-Tolerant Fcility Placement Problem[J]. Operations Research Transactions, 2012, 16(1): 13-20.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/

https://www.ort.shu.edu.cn/EN/Y2012/V16/I1/13

Jain K, Mahdian M, Markakis E, et al. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP [J]. Journal of the ACM, 2003, 50(6): 795-824.
Jain K, Vazirani V V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J]. Journal of the ACM, 2001, 48(2): 274-296.
Mahdian M, Ye Y Y, Zhang J W. Approximation algorithms for metric facility location problems [J]. SIAM Journal on Computing, 2006, 36(2): 411-432.
Li S. A 1.488 approximation algorithm for the uncapacitated facility location problem [C]// Luca Aceto, Proceedings of ICALP, Part II, Switzerland: Springer, 2011, 77-88.
Guha S, Khuller S. Greedy strikes back: improved facility location algorithms [J]. Journal of Algorithms, 1999, 31(1): 228-248.
Byrka J, Aardal K I, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem [J]. SIAM Journal on Computing, 2010, 39(6): 2212-2231.
Shmoys D B, Tardos E, Aardal K I. Approximation algorithms for facility location problems (extended abstract) [C]// F. Tom Leighton, Peter Shor, Proceedings of STOC, Texas: ACM New York, 1997, 265-274.
Sviridenko M. An improved approximation algorithm for the metric uncapacitated facility location problem [C]// William J, Proceedings of IPCO, Cambridge: Springer, 2002, 240-257.
Ageev A, Ye Y Y, Zhang J W. Improved combinatorial apporximation algorithms for the k-level facility location problem [J]. SIAM Journal on Discrete Mathematics, 2004, 18(1): 207-217.
Chen X J, Chen B. Approximation algorithms for soft-capacitated facility location in capacitated network design [J]. Algorithmica, 2007, 53(3): 263-297.
Du D D, Lu R X, Xu D C. A primal-dual approximation algorithm for the facility location problem with submodular penalties [J]. Algorithmica, 2012, 63(1-2): 191-200.
Shu J. An efficient greedy heuristic for warehouse-retailer network design optimization [J]. Transportation Science, 2010, 44(2): 183-192.
Shu J, Teo C P, Max Shen Z J. Stochastic transportation-inventory network design problem [J]. Operations Research, 2005, 53(1): 48-60.
Zhang P. A new approximation algorithm for the k-facility location problem [J]. Theoretical Computer Science, 2007, 384(1): 126-135.
Jain K, Vazirani V V. An approximation algorithms for the fault tolerant metric facility location problem [J]. Algorithmica, 2003, 38(3): 433-439.
Byrka J, Srinivasan A, Swamy C. Fault-tolerant facility location: a randomized dependent LP-rounding algorithm [C]// Friedrich Eisenbrand and F. Bruce, Proceedings of IPCO, Switzerland: Springer, 2010, 244-257.
Guha S, Meyerson A, Munagala K. A constant factor approximation algorithms for the fault tolerant facility location problem [J]. Journal of Algorithms, 2003, 48(2): 449-420.
Swamy C, Shmoys D B. Fault-tolerant facility location [J]. ACM Transactions on Algorithms, 2008, 4(4), Article 51.
Xu S H, Shen H. The fault-tolerant facility allocation problem [C]// Yingfei Dong, Ding-Zhu Du and Oscar Ibarra, Proceedings of ISAAC, Hawaii: Springer, 2009, 689-698.
Ravi R, Sinha A. Hedging uncertainty: approximation algorithms for stochastic optimization problems [J]. Mathmatical Programming, 2006, 108(1): 97-114.
Yan L, Chrobak M. Approximation algorithms for the fault tolerant facility placement problem [J]. Information Processing Letters, 2011, 111(11): 545-549.

[1]	WU Hongyi, WANG Dong, WAN Long, LUO Wenchang. Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions [J]. Operations Research Transactions, 2026, 30(1): 188-196.
[2]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[3]	Jie GAO, Juan ZOU, Yukang SUI, Yuzhong ZHANG. Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection [J]. Operations Research Transactions, 2023, 27(3): 137-149.
[4]	An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN. Maximum matching based approximation algorithms for precedence constrained scheduling problems [J]. Operations Research Transactions, 2022, 26(3): 57-74.
[5]	Dong WANG, Ganggang LI, Wenchang LUO. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes [J]. Operations Research Transactions, 2022, 26(3): 133-142.
[6]	Chunyan BI, Long WAN, Wenchang LUO. Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection [J]. Operations Research Transactions, 2022, 26(2): 73-82.
[7]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[8]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[9]	Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties [J]. Operations Research Transactions, 2022, 26(1): 99-112.
[10]	Jiachen JU, Qian LIU, Zhao ZHANG, Yang ZHOU. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.
[11]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.
[12]	Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[13]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[14]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[15]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.

An Approximation Agorithm for the Stochastic Fault-Tolerant Fcility Placement Problem

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments