# 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. Commented 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.
– user133445
Commented 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. Commented May 2, 2021 at 20:14

## 1 Answer

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$$.

• Could you please clarify this answer, it is not unclear and the variables you are using have not been defined in a meaningful way. It is not clear what i_1, ... i_l is in the second sentence or why the summation x_i1 + ... + x_il >= 1 holds true. Is i_1 an element within subset j? What does x_i1 represent? Why do you take the maximum of x_i1, ..., x_il, what does this maximum value represent?
– user133445
Commented May 2, 2021 at 16:13
• You’ll have to work it out, sorry. Commented May 2, 2021 at 16:20
• Most questions asked here are homework questions, and I don't always want to do someone else's homework. Commented May 2, 2021 at 17:02