LP-Rounding Based Algorithm for Capacitated Uniform Facility Location Problem with Soft Penalties

Capacitated facility location problem (CFLP) is a classical combinatorial optimization problem that has various applications in operations research, theoretical computer science, and management science. In the CFLP, we have a potential facilities set and a clients set. Each facility has a certain capacity and an open cost, and each client has a spliitable demand that need to be met. The goal is to open some facilities and assign all clients to these open facilities so that the total cost is as low as possible. The CFLP is NP-hard (non-deterministic polynomial-hard), and a large amount of work has been devoted to designing approximation algorithms for CFLP and its variants. Following this vein, we introduce a new variant of CFLP called capacitated uniform facility location problem with soft penalties (CUFLPSP), in which the demand of each client can be partially rejected by paying penalty costs. As a result, we present a linear programming-rounding (LP-rounding) based 5.5122-approximation algorithm for the CUFLPSP.