A 3-Approximation Algorithm for Uniform Capacitated Facility Location Problem with Penalties

Abstract

We introduce an algorithm based on local search for “Uniform Capacitated Facility Location Problem with Penalties (UCFLPP)” and analyze the same. The algorithm is same as given by Korupolu et al. for the “Uniform Capacitated Facility Location Problem (UCFLP)”. Aggarwal et al. in their work proved that the algorithm given by Korupolu et al. is a 3-factor approximation algorithm for UCFLP. We extend idea of Aggarwal et al. to show that the same algorithm works for the problem with penalty incorporated. It has the same approximation guarantee for UCFLPP, as given by them. This improves upon the current best of 5.732 factor for the problem, which is an LP based algorithm by Lv and Wu.