An Improved Approximation Algorithm for Uncapacitated Facility Location Problem with Penalties

摘要

In this paper, we consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP for short) in which each client is either assigned to an opened facility or rejected by paying a penalty. We present a 1.8526-approximation algorithm for the UFLWP problem. Our algorithm first enhances the primal-dual method for the UFLWP problem so that outliers can be recognized more efficiently, and then applies a local search heuristic to further reduce the cost for serving those non-rejected clients.