带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法

An approximation algorithm for Robust k-product facility location problem with linear penalties

k-种产品设施选址问题是指存在一组客户和一组可以建设设施的地址。现有k种不同的产品,每一客户均需要k种不同的产品,且每一设施最多只能生产一种产品。问题的要求是从若干地址中选择一组地址来建立设施,对所要建立的设施指定其生产的产品,并为每一个客户提供一组指派确保每一客户都有k个设施来为其提供k种不同的产品,使得设施建设费用与运输费用之和最小。对于k-种产品设施选址问题,我们通常简写为k-PUFLP,其中,当所有设施建设费用为0时,记为k-PUFLPN。本文对k-PUFLPN进行线性舍入,通过分析最优分数解特殊结构,当k≥3时分析算法将k-PUFLPN的近似比从3k/2-1提升到了3k/2-3/2。鲁棒k-种产品设施选址问题是指在该问题中,最多有q个客户可以不被服务。我们首次对无容量限制下建设费用为0时的鲁棒k-种产品选址问题建立模型,当k≥3,得到了3k/2-3/2近似算法。对顾客伴有线性惩罚的鲁棒k-种产品设施选址问题,本文同时考虑异常值与惩罚性,利用k-PUFLPN中最优整数解与最优分数解的关系,得到了3k/2-3/2近似算法。

A k-product facility location problem can be described as follows.There is a set of customers and a set of potential sites where facility can be set up.There are k different products.Each customer needs to be served with all of the k different products and each facility can be set up to provide exact one product.The problem is to select a set of facility to be set up and determine an assignment for each customer to a set of k facilities to provide it with k distinct products.It is assumed that the capacity of any facility is unlimited and there is a non-negative cost for shipping products between each pair of locations.The aim is to minimize the sum of the setup costs and the shipping costs from facilities to customers.For simplicity,we denote the problem by k-PUFLP.When the cost of setting up any facility is zero,we denote by k-PUFLPN.When k≥3,the approximation ratio of an existing algorithm is improved to 3k/2-3/2.When a maximum of q customers are allowed to be unserved,we call it Robust k-product facility location problem.For this problem,we addressed an approximation algorithm with an approximate ratio of 3k/2-3/2.For the Robust k-product facility location problem of linear penalties,by considering both outliers and penalty we also designed a 3k/2-3/2 approximation algorithm.