Improved Local Search Based Approximation Algorithm for Hard Uniform Capacitated k-Median Problem

Abstract

In this paper, we study the hard uniform capacitated $k$ - median problem. We give $(5+\epsilon)$ factor approximation for the problem using local search technique, violating cardinality by a factor of $3$. Though better results are known for the problem using LP techniques, local search algorithms are well known to be simpler. There is a trade-off viz-a-viz approximation factor and cardinality violation between our result and the result of Korupolu \etal \cite{KPR} which is the only result known for the problem using local search. They gave $(1 + \alpha)$ approximation factor with $(5 + 5/\alpha)$ factor loss in cardinality. In a sense, our result is an improvement as they violate the cardinality by more than a factor of $6$ to achieve $5$ factor in approximation. Though in their result, the approximation factor can be made arbitrarily small, cardinality loss is at least $5$ and small approximation factor is obtained at a big loss in cardinality. Thus, we improve upon their result with respect to cardinality.