### Question

In the set cover problem, the goal is to find a collection of subsets indexed by $I$ that minimizes $\sum_{j \in I} w_j$ such that

$\left| \bigcup_{j \in I} S_j \right| = |E|.$Consider the *partial cover* problem, in which one finds a collection of subset indexed by $I$ that minimizes $\sum_{j \in I} w_j$ such that

where $0 < p < 1$ is some constant.

- Give a polynomial-time algorithm to find a solution to the partial cover problem in which the value is no more than $c(p) \cdot$OPT, where $c(p)$ is a constant that depends on $p$, and OPT is the value of the optimal solution to the set cover problem.
- Give an $f(p)$-approximation algorithm for the partial cover problem, such that $f$ is non-decreasing in $p$ and $f(1) \leq H_{E}$.

### Answers

**1.** Consider the greedy algorithm that halts after covering $pn$ elements. Let $n_i$ be the number of elements uncovered in the beginning of the $i$th iteration, then there exists a set $S_j$ such that $w_j \leq |S_j|\frac{OPT}{n_i}$. Let $S_1, \dots, S_{t}$ be the sets chosen by the greedy algorithm (in that order), then the cost of the greedy solution is at most $\sum_{i = 1}^{t - 1} |S_i| \frac{OPT}{n_i} + w_j \leq OPT(H_n - H_{n - np} + 1) \leq OPT(\ln n - \ln(n - np) + 1) = (1 + \ln \frac{1}{1 - p})OPT$.

**2.** Consider a greedy algorithm that in the $i$th iteration chooses

Where $E_i$ is the set of uncovered elements at the beginning of the $i$th iteration and $n_i = np - (n - |E_i|)$.

So the optimal solution covers at least $n_i$ uncovered elements at the beginning of the $i$th iteration and thus the cost to cover the next element(s) by the greedy algorithm is at most $\frac{OPT}{n_i}$ and the total cost is at most $\sum_{i = 1}^np \frac{OPT}{i} = H_{np}$.