带有次模惩罚的k-种产品设施选址问题近似算法  

Algorithm for k-product Facility Location Problem with Submodular Penalties

作　　者：李小玮 成夏炎 李荣珩 LI XIAOWEI;CHENG XIAYAN;LI RONGHENG(Key Laboratory of Computing and Stochastic Mathematics(Ministry of Education),Key Laboratory of Control and Optimization of Complex Systems(University of Hunan Province),College of Mathematics and Statistics,Hunan Normal University,Changsha 410081,China;College of Information Science and Engineering,Hunan First Normal University,Changsha 410205,China)

机构地区：[1]计算与随机数学教育部重点实验室,复杂系统的控制与优化湖南省高校重点实验室,湖南师范大学数学与统计学院,长沙410081 [2]湖南第一师范大学数学与统计学院,长沙410205

出　　处：《应用数学学报》2022年第3期307-321,共15页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(11471110);湖南省教育厅科学研究(16A126,16C0332)资助项目。

摘　　要：本文我们研究了设施建设费用为零时的带线性惩罚的k-种产品设施选址问题与带次模惩罚的k-种产品设施选址问题.在带线性惩罚的k-种产品设施选址问题中,每一客户均对应一定的惩罚费用,目标是选择一个开设的设施集合,将一部分客户连接到开设的设施,使得这些客户对k种产品的需要均得到满足,同时对另一部分客户进行惩罚,并使得客户连接费用与客户惩罚费用之和最小.针对该问题特殊结构,当k≥3时我们得到了(3k/2)-(3/2)近似算法.在带次模惩罚的k-种产品设施选址问题中,客户的每个子集都对应一定的次模惩罚费用,我们给出了该问题的数学规划模型,结合问题的次模性,利用原始对偶算法,当k≥3时得到了(3k/2)-(3/2)近似算法.In this paper,we study the k-product facility location problem with linear penalties and submodular penalties when the cost of setting up any facitity is zero.In the k-product facility location problem with linear penalties,each client has a linear penalty cost,the problem is to select a set of facility to be set up and determine an assignment for some of the clients to a set of k facilities to provide it with k distinct products and penalize the remaining clients.The aim is to minimize the sum of the penalty costs and the shipping costs from facilities to clients.For this problem,we design an approximation algorithm with an approximate ratio of(3k/2)-(3/2)when k≥3.In the k-product facility location problem with submodular penalties,each subset of the clients has a submodular penalty cost.By exploiting the special structure of the problem,whenk≥3,we design a primal-dual approximation algorithm with approximation factor(3k/2)-(3/2).

关 键 词：近似算法 设施选址 原始对偶 

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