Abstract:

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.

Key words: approximation algorithms, facility location, linear penalty