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

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

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

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\geq 3$, the approximation ratio of an existing algorithm is improved to $\frac{3k}{2}-\frac{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 $\frac{3k}{2}-\frac{3}{2}$. For the Robust $k$-product facility location problem of linear penalties, by considering both outliers and penalty we also designed a $\frac{3k}{2}-\frac{3}{2}$ approximation algorithm.