带次模惩罚的优先设施选址问题的近似算法

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

运筹学学报

• 运筹学 • 下一篇

带次模惩罚的优先设施选址问题的近似算法

王颖¹, 王凤敏², 徐大川^2,*, 徐文青^2,3

1. 太原工业学院理学系, 太原 030008; 2. 北京工业大学应用数理学院, 北京 100124; 3. 加州州立大学长滩分校数学与统计系, 加州长滩 90840, 美国

收稿日期:2014-12-01 出版日期:2015-06-15 发布日期:2015-06-15
通讯作者: 徐大川
基金资助:
国家自然科学基金 (No. 11371001)

Approximation algorithms for the priority facility location problem with submodular penalties

WANG Ying¹, WANG Fengmin², XU Dachuan^2,*, XU Wenqing^2,3

1. Department of Science, Taiyuan Institute of Technology, Taiyuan 030008, China; 2. College of Applied Sciences, Beijing University of Technology, Beijing 100124, China; 3. Department of Mathematics and Statistics, California State University, Long Beach, CA 90840, USA

Received:2014-12-01 Online:2015-06-15 Published:2015-06-15

摘要/Abstract

摘要：

研究带次模惩罚的优先设施选址问题, 每个顾客都有一定的服务水平要求, 开设的设施只有满足了顾客的服务水平要求, 才能为顾客提供服务, 没被服务的顾客对应一定的次模惩罚费用. 目标是使得开设费用、连接费用与次模惩罚费用之和最小. 给出该问题的整数规划、线性规划松弛及其对偶规划. 基于原始对偶和贪婪增广技巧, 给出该问题的两个近似算法, 得到的近似比分别为3和2.375.

关键词: 次模惩罚, 优先设施选址, 原始对偶, 贪婪增广, 近似算法

Abstract:

In this paper, we study priority facility location problem with submodular penalties where each client has a level-of-service requirement. An open facility must satisfy the requirement of the clients served by it, and there is a submodular penalty cost corresponding with the unserved clients. The objective is to minimize the sum of the opening cost, the connection cost and the submodular penalty cost. We present the integer program, the linear programming relaxation and the dual program for the problem. Using the primal-dual and greedy augmentation techniques, we then propose two approximation algorithms and obtain the approximation ratios of 3 and 2.375 respectively.

Key words: submodular penalties, priority facility location, primal-dual, greedy augmentation, approximation algorithm

王颖, 王凤敏, 徐大川, 徐文青. 带次模惩罚的优先设施选址问题的近似算法[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2015.02.001.

WANG Ying, WANG Fengmin, XU Dachuan, XU Wenqing. Approximation algorithms for the priority facility location problem with submodular penalties[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2015.02.001.

参考文献

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

Jain K, Mahdian M, Saberi A. A new greedy approach for facility location problems [C]// Proceedings of the 34th ACM Symposium on Theory of Computing, New York: Association for Computing Machinery, 2002, 731-740.

Li S. A 1.488 approximation algorithm for the uncapacitated facility location problem [C]//Proceedings of the 38th International Colloquium on Automata, Languages and Programming, Part II, Springer, LNCS 6756, 2011, 77-88.

Jain K, Vazirani V V. Primal-dual 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: 274-296.

Guha S, Khuller S. Greedy strike back: Improved facility location algorithms [J]. Journal of Algorithms, 1999, 31: 228-248.

Charikar M, Guha S. Improved combinatorial algorithms for facility location problems [J]. SIAM Journal on Computing, 2005, 34: 803-824.

Charikar M, Khuller S, Mount D M, et al. Algorithms for facility location problems with outliers [C]// Proceedings of SODA, PA, USA: Society for Industrial and Applied Mathematics Philadelphia, 2001, 642-651.

Chudak F A, Nagano K. Efficient solutions to relaxations of combinatorial problems with submodular penalties via the lovasz extension and non-smooth convex optimization [C]//Proceedings of SODA, PA, USA: Society for Industrial and Applied Mathematics Philadelphia, 2007, 79-88.

Hayrapetyan A, Swamy C, Tard\ddot{o}s \'{E}. Network design for information networks [C]// Proceedings of SODA, PA, USA: Society for Industrial and Applied Mathematics Philadelphia, 2005, 933-942.

Fujishige S. Submodular Functions and Optimization [M]. Elsevier, 2005.

Du D L, Lu R X, Xu D C. A primal-dual approximation algorithm for the facility location problem with submodular penalties [J]. Algorithmica, 2012, 63: 191-200.

Li Y, Du D L, Xiu N H, et al. A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties [J]. Theoretical Computer Science, 2013, 476: 109-117.

Ravi R, Sinha A. Approximation algorithms for multicommodity facility location problems [J]. SIAM Journal on Discrete Mathematics, 2010, 24: 538-551.

Mahdian M. Facility location and the analysis of algorithms through factor-revealing programs [D]. Massachusetts Institute of Technology, 2004.

Li G D, Wang Z, Wu C C. Approximation algorithms for the stochastic priority facility location problem [J]. Optimization, 2013, 62(7): 919-928.

Wang F M, Xu D C, Wu C C. Approximation algorithms for the priority facility location problem with penalties [J]. Journal of Systems Science and Complexity, 2014, DOI: 10.1007/s11424-014-2157-2.

Fleischer L, Iwata S. A push-relabel framework for submodular function minimization and applications to parametric optimization [J]. Discrete Applied Mathematics, 2003, 131: 311-322.

[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): 116-122.
[14]	徐大川, 万玮, 吴晨晨, 徐文青. 随机容错设施选址问题的原始-对偶近似算法[J]. 运筹学学报, 2014, 18(2): 17-28.
[15]	李浙宁，凌晨，王宜举，杨庆之. 张量分析和多项式优化的若干进展[J]. 运筹学学报, 2014, 18(1): 134-148.

带次模惩罚的优先设施选址问题的近似算法

Approximation algorithms for the priority facility location problem with submodular penalties

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价