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

运筹学学报 ›› 2012, Vol. 16 ›› Issue (1): 13-20.

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

邵嘉婷¹, 徐大川¹

1. 北京工业大学数理学院, 北京, 100124

收稿日期:2011-09-23 修回日期:2011-12-19 出版日期:2012-03-15 发布日期:2012-03-15
通讯作者: 徐大川 E-mail:xudc@bjut.edu.cn

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

SHAO Jiating¹, Xu Dachuan¹

1. Department of Applied Mathematics, Beijing University of Technology, Beijing 100124, China

Received:2011-09-23 Revised:2011-12-19 Online:2012-03-15 Published:2012-03-15
Supported by:
This work is supported by The National Science Foundation of China (No. 11071268), Scientific Research Common Program of Beijing Municipal Commission of Education (No. KM201210005033), and PHR(IHLB).

摘要/Abstract

摘要： 在确定性的容错设施布局问题中, 给定顾客的集合和地址的集合. 在每个地址上可以开设任意数目的不同设施. 每个顾客j有连接需求r_j. 允许将顾客j连到同一地址的不同设施上. 目标是开设一些设施并将每个顾客j连到r_j个不同的设施上, 使得总开设费用和连接费用最小. 研究两阶段随机容错设施布局问题(SFTFP), 顾客的集合事先不知道, 但是具有有限多个场景并知道其概率分布. 每个场景指定需要服务的顾客的子集. 并且每个设施有两种类型的开设费用. 在第一阶段根据顾客的随机信息确定性地开设一些设施, 在第二阶段根据顾客的真实信息再增加开设一些设施．给出随机容错布局问题的线性整数规划和基于线性规划舍入的5-近似算法.

关键词: 设施布局问题 , , 近似算法, , 线性规划舍入

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

邵嘉婷, 徐大川. 随机容错设施布局问题的近似算法[J]. 运筹学学报, 2012, 16(1): 13-20.

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.

参考文献

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]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[2]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[3]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[4]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[5]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[6]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[7]	王一水, 徐大川, 吴晨晨. 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018, 22(1): 67-76.
[8]	陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114.
[9]	仲维亚, 马晓茹. 带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报, 2016, 20(4): 93-101.
[10]	孙婷, 李改弟, 徐文青. 最大割问题和最大平分割问题基于半定规划松弛的近似算法[J]. 运筹学学报, 2016, 20(3): 21-32.
[11]	方芮, 罗文昌. 带惩罚的容错设施布局问题的近似算法[J]. 运筹学学报, 2016, 20(2): 69-78.
[12]	闫林成, 肖汉, 赵红娟, 孙小淇. 关于可靠性设施布局问题的近似算法[J]. 运筹学学报, 2015, 19(4): 14-24.
[13]	陈宁, 孙文瑜, 袁锦昀. 解线性等式约束优化问题的模式搜索过滤集方法[J]. 运筹学学报, 2015, 19(3): 96-107.
[14]	范静, 张峰. 具有多个不可用时间段的单机供应链排序问题[J]. 运筹学学报, 2015, 19(3): 116-122.
[15]	王颖, 王凤敏, 徐大川, 徐文青. 带次模惩罚的优先设施选址问题的近似算法[J]. 运筹学学报, 2015, 19(2): 1-14.