Approximation of the capacitated set cover problem 1,2

This paper considers the capacitated set cover problem which is an extension of the set cover problem, in which each item has a splittable demand and each set, whose multiple copies are allowed, has a fixed capacity. Compared to the previous algorithm whose approximation factor depends on the capacity of sets, our factors depend only on k, the maximum cardinality of a set. They are (1 +Hk) and 2Hk, respectively, for the unweighted and weighted case where Hk = 1 + 12 + · · ·+ 1k. Key words: capacitated set cover problem, approximation algorithm, batch consolidation problem