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

Approximation algorithms for the priority facility location problem with submodular penalties

作　　者：王颖[1] 王凤敏[2] 徐大川[2] 徐文青[2,3] 

机构地区：[1]太原工业学院理学系,030008 [2]北京工业大学应用数理学院,北京100124 [3]加州州立大学长滩分校数学与统计系

出　　处：《运筹学学报》2015年第2期1-14,共14页Operations Research Transactions

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

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

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

分 类 号：O221.7[理学—运筹学与控制论]