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