带惩罚的容错设施布局问题的近似算法

doi:10.15960/j.cnki.issn.1007-6093.2016.02.006

运筹学学报

带惩罚的容错设施布局问题的近似算法

方芮¹ 罗文昌^1,*

1. 宁波大学理学院, 浙江宁波 315211

收稿日期:2015-09-14 出版日期:2016-06-15 发布日期:2016-06-15
通讯作者: 罗文昌 E-mail: luowenchang@163.com
基金资助:
宁波大学科研基金(No. XKl15D218)

Approximation algorithm for the fault-tolerant facility placement problem with penalties

FANG Rui¹LUO Wenchang^1,*

1. Faculty of Science, Ningbo University, Ningbo 315211, Zhejiang, China

Received:2015-09-14 Online:2016-06-15 Published:2016-06-15

摘要/Abstract

摘要：

在带惩罚的容错设施布局问题中, 给定顾客集合、地址集合、以及每个顾客和各个地址之间的连接费用, 这里假设连接费用是可度量的. 每位顾客有各自的服务需求, 每个地址可以开设任意多个设施, 顾客可以被安排连接到某些地址的一些开设的设施上以满足其需求, 也可以被拒绝, 但这时要支付拒绝该顾客所带来的惩罚费用. 目标是确定哪些顾客的服务需求被拒绝并开设一些设施, 将未被拒绝的顾客连接到不同的开设设施上, 使得开设费用、连接费用和惩罚费用总和最小. 给出了带惩罚的容错设施布局问题的线性整数规划及其对偶规划, 进一步, 给出了基于其线性规划和对偶规划舍入的4-近似算法.

关键词: 容错设施布局问题, 惩罚, 舍入, 近似算法

Abstract:

In the fault-tolerant facility placement problem with penalties, we are given a set of customers and a set of sites, and connection costs between customers and sites. We assume that the connection costs satisfy the metric principle. Each customer has its service demands. We can open an unbounded number of different facilities at each site. Each customer can be either assigned to some different opened facilities in some sites to satisfy its demands or rejected by paying a penalty. The objective is to minimize the total cost of opening facilities and connecting those non-rejected customers to different open facilities, and the reject penalties. In this paper, we formulate the fault-tolerant facility placement problem with penalties as a linear integer programming and give its dual programming. Then we propose a 4-approximation algorithm based on rounding its linear programming and dual programming.

Key words: fault-tolerant facility placement problem, penalties, rounding, approximation algorithm

方芮, 罗文昌. 带惩罚的容错设施布局问题的近似算法[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2016.02.006.

FANG Rui, LUO Wenchang. Approximation algorithm for the fault-tolerant facility placement problem with penalties[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.02.006.

参考文献

[1] Shmoy D B, Tard\ddot{\mathrm o}s \acute{\mathrm E}, Aardal K I. Approximation algorithms for facility location problems [C]// Proceedings of STOC, New York: ACM, 1997, 265-274.

[2] Guha S, Khuller S. Greedy strikes back: improved facility location algorithms [J]. Journal of Algorithms, 1999, 31(1): 228-248.

[3] Sviridenko M. An improved approximation algorithm for the metric uncapacitated facility location problem [C]//Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization, 2002, 240-257.

[4] Chudak F A, Shmoy D B. Improved approximation algorithm for the uncapacitated facility location problem [J]. SIAM Journal on Computing, 2003, 33(1): 1-25.

[5] Mahdian M, Ye Y, Zhang J. Approximation algorithms for metric facility location problems [J]. SIAM Journal on Computing, 2006, 36(2): 411-432.

[6] Byrka J, Aardal K. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem [J]. SIAM Journal on Computing, 2010, 39(6): 2212-2231.

[7] Li S. A 1.488 approximation algorithm for the uncapacitated facility location problem [J]. Information and Computation, 2013, 222: 45-58.

[8] Jain K, Vazirani V V. An approximation algorithm for the fault tolerant metric facility location problem [J]. Algorithmica, 2003, 38(3): 433-439.

[9] 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): 433-439.

[10] Swamy C, Shmoy D B. Fault-tolerant facility location [J]. ACM Transactions on Algorithms, 2008, 4(4): 1-27.

[11] Byrka J, Srinivasan A, Swamy C. Fault-tolerant facility location: a randomized dependent LP-rounding algorithm [C]//Proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization, 2010, 244-257.

[12] Xu S, Shen H. The fault-tolerant facility allocation problem [C]//Proceedings of the 20th International Symposium on Algorithms and Computation, 2009, 689-698.

[13] Yan L, Chrobak M. Approximation algorithms for the fault-tolerant facility placement problem [J]. Information Processing Letters, 2011, 111: 545-549.

[14] Shao J, Xu D. An Approximation algorithm for the stochastic fault-tolerant facility placement problem [J]. Opeartions Research Transaction, 2012, 16: 13-20.

[15] Xu G, Xu J. An LP rounding algorithm for approximating uncapacitated facility location problem with penalties [J]. Information Processing Letters, 2005, 94: 119-123.

带惩罚的容错设施布局问题的近似算法

Approximation algorithm for the fault-tolerant facility placement problem with penalties

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[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]. 运筹学学报, 2017, 21(2): 84-100.
[9]	陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114.
[10]	仲维亚, 马晓茹. 带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报, 2016, 20(4): 93-101.
[11]	孙婷, 李改弟, 徐文青. 最大割问题和最大平分割问题基于半定规划松弛的近似算法[J]. 运筹学学报, 2016, 20(3): 21-32.
[12]	闫林成, 肖汉, 赵红娟, 孙小淇. 关于可靠性设施布局问题的近似算法[J]. 运筹学学报, 2015, 19(4): 14-24.
[13]	范静, 张峰. 具有多个不可用时间段的单机供应链排序问题[J]. 运筹学学报, 2015, 19(3): 116-122.
[14]	王颖, 王凤敏, 徐大川, 徐文青. 带次模惩罚的优先设施选址问题的近似算法[J]. 运筹学学报, 2015, 19(2): 1-14.
[15]	徐大川, 万玮, 吴晨晨, 徐文青. 随机容错设施选址问题的原始-对偶近似算法[J]. 运筹学学报, 2014, 18(2): 17-28.