English

运筹学学报 >

2016 , Vol. 20 >Issue 2: 69 - 78

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.02.006

运筹学

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

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

收稿日期: 2015-09-14

  网络出版日期: 2016-06-15

基金资助

宁波大学科研基金(No. XKl15D218)

收起

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

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

Received date: 2015-09-14

  Online published: 2016-06-15

Fold

摘要

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

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

本文引用格式

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

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

参考文献

[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.
 
Options
文章导航

/

〈 〉