LOCAL SEARCH ALGORITHM FOR THE SQUARED METRIC k-FACILITY LOCATION PROBLEM WITH LINEAR PENALTIES

In the k-facility location problem, an important combinatorial optimization problem combining the classical facility location and k-median problems, we are given the locations of some facilities and clients, and need to open at most k facilities and connect all clients to opened facilities, minimizing the facility opening and connection cost. This paper considers the squared metric k-facility location problem with linear penalties, a robust version of the k-facility location problem. In this problem, we do not have to connect all clients to facilities, but each client that is not served by any facility must pay a penalty cost. The connection costs of facilities and clients are supposed to be squared metric, which is more general than the metric case. We provide a constant approximation algorithm based on the local search scheme with add, drop, and swap operations for this problem. Furthermore, we improve the approximation ratio by using the scaling technique.