202309281909

Tags : Advanced Algorithms

Set Cover Problem

---

Universe $U=\{e_1,\dots ,e_n\}$ Family of subsets of $U$, $\mathcal{F}=\{S_1,\dots ,S_i\}$, $S_i\subset U\forall i$, $\bigcup _{S_i\in \mathcal{F}}{S}_i=U$. Cost $c:\mathcal{F}\to Q^{+}$ Goal: Pick a minimum size subcollection ${\mathcal{F}}^{\prime }\subset \mathcal{F}$ s.t. union of the collection is $U$.

• NP hardness follows because of reduction to this from vertex cover.

Greedy Algorithm

$R:$ Set of elements covered so far $R=\varphi ,{\mathcal{F}}^{\prime }=\varphi$ while $R\ne U$, Find the most cost-effective set $S$. ($S$ has min value of $\frac{c(S)}{|S\setminus R|}={\alpha }_S$), add to ${\mathcal{F}}^{\prime }$. (Resolve ties arbitrarily.) $R=S\cup R$. output ${\mathcal{F}}^{\prime }$.

Analysis: (For a specific rum) $S\setminus R:$ uncovered elements so far For each element in $S\setminus R$, set $\text{price}(e)={\alpha }_S$.

$\text{cost}({\mathcal{F}}^{\prime })=\sum _{i=1}^n\text{price}(e_i)=\sum _{S\in {\mathcal{F}}^{\prime }}c(S)$.

Arrange elements of $V$ in the order in which they are covered in the algorithm, say $e_1,\dots ,e_n$. Observe: Before the iteration in which $e_k$ is covered, there are $\ge n-k+1$ uncovered elements.

Price Upper Bound

Claim: $\text{price}(e_k)\le \frac{OPT}{n-k+1}$

Proof: $\text{price}(e_1)\le \frac{OPT}{n}$ (It is equal if the first set is U. The other sets would have at least as much mean cost as the price of $e_1$.) Assume that we get the $k-1$ elements for free. This gives the bound using the same argument as above. We can assume that because otherwise we’ll have $OPT-x$ on the RHS which is only better!

$$\begin{array}{rl}\text{cost}({\mathcal{F}}^{\prime })& =\sum _{k=1}^n\text{price}(e_k)\\ & \le \sum _{k=1}^n\frac{\text{cost}(OPT)}{n-k+1}\\ & =\text{cost}(OPT)\sum _{i=1}^n\frac{1}{i}\\ & \le \text{cost}(OPT).\log (n)\end{array}$$

Tightness example

Consider $\mathcal{F}=\{S_i\}.S_1=\{1\},S_2=\{2\},\dots ,S_n=\{n\},S_{n+1}=\{1,2,\dots ,n\}.$ c(S_{i})= \left\{ \begin{align*} \frac{1}{i}, && 1\le i\le n\\ 1+\epsilon, && i=n+1\\ \end{align*} \right.

Thus the analysis is tight and we get an $H_n-$approximation.

---

References

Approximation Algorithms Vertex Cover Problem → Travelling Salesman Problem