English

运筹学学报 >

2015 , Vol. 19 >Issue 2: 1 - 14

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

运筹学

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

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

收稿日期: 2014-12-01

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

基金资助

国家自然科学基金 (No. 11371001)

收起

 Approximation algorithms for the  priority facility location problem with submodular penalties

Expand
  • 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 date: 2014-12-01

  Online published: 2015-06-15

Fold

摘要

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

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

本文引用格式

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

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

参考文献

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.

 
Options
文章导航

/

〈 〉