1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Solve the LP and round the solution. $\endgroup$ May 2 at 5:16
  • $\begingroup$ @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. $\endgroup$
    – x1839654x
    May 2 at 15:13
  • 2
    $\begingroup$ 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. $\endgroup$
    – Raphael
    May 2 at 20:14
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – x1839654x
    May 2 at 16:13
  • $\begingroup$ You’ll have to work it out, sorry. $\endgroup$ May 2 at 16:20
  • $\begingroup$ Most questions asked here are homework questions, and I don't always want to do someone else's homework. $\endgroup$ May 2 at 17:02

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.