Approximation Algorithm for the k-Product Uncapacitated Facility Location Problem with Penalties

In the k-product uncapacitated facility location problem with penalties, we are given a set of demand points where clients are located and a set of potential sites where facilities with unlimited capacities can be opened. There are k different kinds of products to be supplied by a set of open facilities. Each open facility can supply only a distinct product with a non-negative fixed cost determined by the product it wants to supply. Each client is either supplied with k kinds of products by a set of k different open facilities or completely rejected. There is a non-negative service cost between each pair of locations and also a penalty cost for each client if its service is rejected. These service costs are assumed to be symmetric and satisfy the triangle inequality. The goal is to select a set of clients to reject their service and then choose a set of facilities to be opened to service the remaining clients so that the total cost of opening facilities, servicing the clients, and the penalty is minimized. We address two different integer programs to describe the problem. Based on the linear programming rounding technique, we propose a (2k + 1)-approximation algorithm for this problem.