2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 13 '16 at 23:00
  • $\begingroup$ @YuvalFilmus Thanks! Do you have a paper reference? $\endgroup$ – Ryan Dec 13 '16 at 23:01
  • $\begingroup$ My guess is that the lower bounds will still work. You can start by checking if Feige's construction is uniform. $\endgroup$ – Yuval Filmus Dec 13 '16 at 23:02
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 13 '16 at 23:04
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.