"Uniform" Set Cover Approximation?

Question

The (optimization version of) Set Cover problem is the following: given a "universe" set $S$ and a collection of subsets $S_1, \cdots, S_m \subseteq S$, we want to find the minimum cardinality set of $k$ elements $\{i_1, \cdots, i_k\}$ such that $\bigcup_{i=1}^k S_{i_j} = S$.

It is a well-known result in an introductory approximation algorithms class that this problem has no $O(\log n)$-factor approximation unless $P = NP$.

However, I'm interested in a restricted version of the problem: suppose that $|S_i| = n$ for all $i$ (i.e., all the subsets are exactly the same size). This problem turns out to still be $NP$-complete, but is there a better approximation ratio one can achieve?

I don't know if there is terminology for the problem (I dubbed it "uniform" here), because searching through Google Scholar and the arXiv has not yielded much.

Answer 1

No, one can't achieve a better approximation ratio for your problem. This follows by a simple padding argument.

Let $S_1^*,\dots,S_m^* \subseteq S^*$ be an instance of ordinary set cover (where the sizes of the sets are not restricted to be the same). Let $n = |S|$. Define $S^* = S \cup \{1,2,\dots,n\}$ where it is assumed that $1,2,\dots,n$ represent $n$ new symbols not found in $S$. Also define $S_i = S^*_i \cup \{1,2,\dots,n-|S^*_i|\}$ and $S_{m+1} = \{1,2,\dots,n\}$. Then $S_1,\dots,S_m,S_{m+1} \subseteq S$ form an instance of your uniform set cover problem; by construction, the sets $S_1,\dots,S_m$ all have the same size. Moreover, the minimum cardinality cover for the original problem $S^*$ differs in size from the minimum cardinality cover for the uniform problem $S$ by at most one, since given any solution $\{i_1,\dots,i_k\}$ for the original problem we obtain a valid solution $\{i_1,\dots,i_k,m\}$ for the uniform problem, and vice versa, any valid solution for the uniform problem is also a solution for the original problem.

It follows from this reduction that uniform set cover has the same approximation factor as ordinary set cover. Thus, all the standard approximability results for set cover carry over to your problem as well.