(untitled) (Informatica, 2018)
In this paper, we study the hard uniform capacitated k - median problem. We give (5+ε) 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 KPR which is the only result known for the problem using local search. They gave (1 + α) approximation factor with (5 + 5/α) 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.