# “Uniform” Set Cover Approximation?

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.

• Actually it has a $\ln n$ factor approximation, but no $(1-\epsilon)\ln n$ factor approximation unless P=NP. This version is a pretty recent result, by the way. – Yuval Filmus Dec 13 '16 at 23:00
• @YuvalFilmus Thanks! Do you have a paper reference? – Ryan Dec 13 '16 at 23:01
• My guess is that the lower bounds will still work. You can start by checking if Feige's construction is uniform. – Yuval Filmus Dec 13 '16 at 23:02
• The tight result is essentially due to Moshkovitz, together with a technical result of Dinur and Steurer. The construction you need to check is in Moshkovitz's paper. – Yuval Filmus Dec 13 '16 at 23:04

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.