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

Algorithm for k-product Facility Location Problem with Submodular Penalties

本文我们研究了设施建设费用为零时的带线性惩罚的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).