2-approximation algorithm for soft-capacitated facility location problem with linear penalties

Abstract In this paper, we will be discussing an extension of the classical facility location problem known as the soft-capacitated facility location problem with linear penalties. In this problem, some demand points are allowed to be abandoned under the condition of paying them established linear penalties. Each facility has its own inherent capacity limit, but each facility can be opened multiple times, just paying a corresponding multiple of the opening cost. This problem is a generation of the uncapacitated facility location with linear penalties. To solve this problem, we present a 2-approximation algorithm by reduction technique, and prove that the algorithm achieves the integrality gap of its standard linear programming relaxation. This means that if the value of the objective function corresponding to the optimal solution of the standard linear relaxation of the soft-capacitated facility location problem with linear penalties is used as the lower bound, a better approximation ratio will not be obtained.