# k-polynomial time approximation algorithm for set cover (k = max size of subsets)

Problem Definition: Given a universe set $$U = \{1, 2, \dots, n\}$$ and a collection of $$m$$ subsets $$S_1, S_2, \dots S_m \subseteq U$$, find the minimum collection of subsets that cover $$U$$.

I am specifically trying to find a $$k$$ polynomial time approximation algorithm for set cover where $$k$$ is the largest size of the subsets. In other words, $$k = \max_{i=1}^m|S_i|$$

I have the following ILP and relaxed LP programs as shown at the end of page 1 and start of page 2 from these lecture notes of Luca Trevisan.

I know that the factor of the polynomial time approximation algorithm depends on the rounding factor necessary in the LP. In the case for weighted set cover, the rounding factor would depend on $$m$$, the number of subsets.

I have determined a lower bound on the number of subsets based on the defined $$k$$ to be as follows: $$\lceil \frac{n}{k} \rceil \leq m$$.

I don't know how to use this (or if this is the correct relationship) to show something along the lines of $$A(I) \leq \alpha OPT(I)$$ where $$A(I)$$ is the approximation algorithm solution, $$OPT(I)$$ is the optimal solution, and $$\alpha$$ is related to $$k$$.

How would you go about solving this problem?

• Solve the LP and round the solution. May 2, 2021 at 5:16
• @YuvalFilmus That is not helpful. I am aware that I need to solve the LP and round the solution. I have stated that in my problem description. I am asking what the rounding factor should be with respect to k. May 2, 2021 at 15:13
• Note that deleting questions after receiving answers is against site policy. If you don't want public record of having gotten help with your homework, don't get help.
– Raphael
May 2, 2021 at 20:14

Let $$A = \{ i : x_i \geq 1/k \}$$. By construction, $$|A| \leq k \sum_i x_i \leq k \mathrm{OPT}$$. The set $$A$$ is a set cover, since if $$S_j = \{i_1,\ldots,i_\ell\}$$ (where $$\ell \leq k$$) then $$x_{i_1} + \cdots + x_{i_\ell} \geq 1$$, and so $$\max(x_{i_1},\ldots,x_{i_\ell}) \geq 1/\ell \geq 1/k$$.