%Created by Deeparnab Chakrabarty, 14th December, 2021
%Modified by Deeparnab Chakrabarty, 

\documentclass[11pt]{article}
\def\lecnumber{1}
\def\lecdate{}
\def\lectopic{Greedy Approximation Algorithm for Set Cover}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{starter}
\newcommand{\solution}[1]{\ignore{#1}}




\begin{document}
	\def\moddate{1st Jan, 2022}
	\header

\begin{itemize}
\item In the set cover problem, we are given a universe $U$ of $n$ elements, and a collection of subsets $\{S_1,\ldots,S_m\}$ of the universe, the goal
is to pick the smallest number of sets from among this collection so that their union is the whole universe. More precisely, we need to find\footnote{$[m]$ denotes $\{1,2,\ldots, m\}$.} $I\subseteq [m]$
such that $\bigcup_{j\in I} S_i = U$. Note that we may assume $\bigcup_{i=1}^m S_i = U$, otherwise we can simply answer no solution.

\remark{There is a weighted generalization where each subset $S_i$ also has a cost $c(S_i)$ and the objective is to minimize the total cost of the sets 
	picked. We will also consider this version.}

\item The Set Cover problem is one of the {\bf \em canonical} problems in approximation algorithms. It generalizes many different problems and arises in many applications. 
One example is task assignment : you have $n$ jobs and $m$ workers, and worker $i$ can perform the subset $S_i$ of the jobs. What is the minimum number of workers you need to complete all jobs?
Another is the vertex cover problem : the universe now is the collection of edges in a graph $G = (V,E)$, and the subsets $S_v$ corresponding to vertex $v$ are the set of edges incident on $v$. What is the minimum number of vertices $C$ such that every edge is incident on at least one vertex in $C$? Since vertex cover is NP-hard, so is set cover.

\exer{\Coffeecup~ Given an undirected graph $G = (V,E)$, a {\bf \em dominating set} $U$ is a subset of $V$ such that every vertex of $V$ is either in $U$ or has a neighbor in $U$. Explain why the minimum cardinality dominating set is a set cover problem.}

Set Cover is also canonical in that many algorithmic ideas from approximation algorithms can be illustrated using this problem. It is also one of the oldest problems for which approximation algorithms were studied. And indeed the most natural algorithm for the problem turns out to be pretty good.

\item {\bf The Greedy Algorithm.}
 \begin{mdframed}[backgroundcolor=green!10,topline=false,bottomline=false,leftline=false,rightline=false] 
	\begin{center}
		\fbox{%
			\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
				\begin{algorithmic}[1]
					\Procedure{Greedy Set Cover}{$U, (S_1, \ldots, S_m)$}:  
					\State Initialize $X \eq U$. \Comment{$X$ will denote the collection of {\bf \em uncovered} elements.}
					\State Initialize $I \eq \emptyset$. \Comment{$I$ denotes the {\em indices} of the sets picked in our solution.}
					\While{$X\neq \emptyset$}:
						\State Pick $j\in [m]$ which maximizes $|S_j \cap X|$. \LineComment{That is, the set which covers the maximum number of uncovered elements.}
						\State $I \eq I \cup j$.
						\State $X \eq X \setminus S_j$.
					\EndWhile
					\State \Return $I$.
					\EndProcedure
				\end{algorithmic}
			\end{varwidth}%
		}
	\end{center}
\end{mdframed}
\begin{thm}
	{\sc Greedy Set Cover} is a $\ln n$-approximation algorithm for the set cover problem.
\end{thm}
\begin{proof}
	Fix an instance $(U, (S_1, \ldots, S_m)$). 
	Let $O \subseteq [m]$ be the optimum solution, and let $k = |O|$. Let $I$ denote the set cover returned by the algorithm. We need to prove $|I| \leq \left(1 + \ln n\right) \cdot |O|$.
	
	To this end, let $x_j$ denote the number of set of uncovered elements {\em before} the $j$th while loop, and let $n_j$ denote the number of elements we cover in the $j$th while loop.
In other words, $x_j = |X|$ before the $j$th while loop, and $n_j = |S_j \cap X|$ where $S_j$ is the set the greedy algorithm picks in the $j$th while loop. Note that $|I|$ is the number of while loops.
Now, the $x_j$ and $n_j$'s satisfy the following.
\begin{equation}\label{eq:recurrence}
x_1 = n;~~~ x_{j+1} = x_j - n_j; ~~~~ n_j \geq \frac{x_j}{k}
\end{equation}
The first two follow from definition. The third is where we use the ``greediness'' of the algorithm and is key to the analysis. Why is it true? Well, $x_j$ is the number of uncovered elements 
at the beginning of loop $j$. We know that the sets of the optimal set cover indexed by $O$ covers all these elements. Therefore, some $S_t$ for $t\in O$ must cover at least $\frac{1}{k}$th of these elements. That is, there exists $t\in O$ with $|S_t \cap X| \geq \frac{x_j}{k}$. The algorithm picks $S_j$ with $|S_j \cap X| \geq |S_t \cap X|$, implying $n_j \geq x_j/k$. 

The rest of the analysis is ``playing around'' with \eqref{eq:recurrence}. We claim the following, and the interested reader may want to prove this on their own.
\begin{claim}\label{clm:mucking-around}
	For any $1\leq j\leq |I|$, $x_j \leq n\cdot \left(1 - \frac{1}{k}\right)^{j-1}$.
\end{claim}
We prove the claim later. We now explain why the claim implies $|I| \leq \ln n \cdot k$. Suppose not, and say $|I| \geq k\ln n + 1$.
At the beginning of the $\ell := |I|$th loop, by~\Cref{clm:mucking-around},  we have 
\[
x_\ell \leq n\cdot \left(1 - \frac{1}{k}\right)^{k\ln n} < n \cdot e^{-\ln n} = 1
\]
where we have used the oft used and very important inequality ``for every real $z \neq 0$, $(1 + z) < e^z$'' with $z = -1/k$. However, $x_\ell < 1$, which implies $x_\ell = 0$ since $x_\ell$ is an integer, is a contradiction : that would mean $X = \emptyset$ at the beginning of the while loop, and so the loop would terminate.
\end{proof}

\exer{ \Coffeecup ~
	Show that one can analyze a bit better : argue that $|I| \leq k\cdot (1 + \ln\left(n/k)\right)$. Furthermore, use this to argue that if every set $|S_i| \leq d$, then 
{\sc Greedy Set Cover} is in fact an $(1 + \ln d)$-approximation algorithm. 
}

\exer{ \Coffeecup~
Prove~\Cref{clm:mucking-around} using induction and \eqref{eq:recurrence}.}

\exer{ \Coffeecup \Coffeecup ~
	The {\sc Max-Coverage} problem has the same input as set cover, but with an extra parameter $k$ which is a positive integer in $[m]$.
	The objective is to pick $k$ sets, indexed by $I$ with $|I| = k$ such that $|\bigcup_{j\in I} S_j|$ is maximized. 
	Describe a natural greedy algorithm for this problem and prove that is an $(1 - \frac{1}{e})$-approximation.
}

\item {Tightness of Analysis.} Whenever one analyses an algorithm, one needs to also wonder if one can do better. In approximation algorithms, where inequalities abound, one could wonder perhaps some inequality is ``loose'', and perhaps with some more cleverness one can say something better. For instance, the $\ln n$-factor is loose in the sense that the above exercise
could improve to $1 + \ln d$-factor which is way better when the subsets are of small size. Can one do even better? Unfortunately, the answer is in the negative.
The following picture illustrates this.

\begin{figure}[ht!]
	\includegraphics[trim = 70 280 0 100, clip, scale = 0.6]{./figs/set-cover-bad-example}
	\caption{\em The optimum solution is to pick the $2$ blue horizontal sets. The greedy algorithm picks the 
	$4$ red ``fatter'' sets. Do you see why? This shows that the approximation factor of the algorithm is at least $2$. Now consider the situation where
we have $2^\ell-1$ points in each row. The optimum solution still picks the two horizontal sets, but the algorithm would end up picking $\ell$ sets. This shows
that the factor is at least $\frac{\log_2(1+d)}{2}$. Now consider what happens when there are $k$-horizontal lines. How would the construction change? }
\end{figure}

\end{itemize}

\section*{The Weighted Version}

\begin{itemize}
	\item Suppose now that every set $S_j$ also had a cost $c(S_j)$, and the objective was to pick the minimum {\em cost} set cover. One then modifies the 
	above algorithm in the obvious way : in the while loop, instead of picking the set which maximizes the number of new elements covered, one picks the set
	which has the best ``bang-for-the-buck'', that is, maximizes the number of new elements covered divided by the cost of the set. For simplicity of the analysis, 
	we describe the algorithm using the reciprocal. 
	 \begin{mdframed}[backgroundcolor=green!10,topline=false,bottomline=false,leftline=false,rightline=false] 
		\begin{center}
			\fbox{%
				\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
					\begin{algorithmic}[1]
						\Procedure{Weighted Greedy Set Cover}{$U, (S_1, \ldots, S_m)$ + costs}:  
						\State Initialize $X \eq U$. \Comment{$X$ will denote the collection of {\bf \em uncovered} elements.}
						\State Initialize $I \eq \emptyset$. \Comment{$I$ denotes the {\em indices} of the sets picked in our solution.}
						\While{$X\neq \emptyset$}:
							\State Pick $j\in [m]$ which minimizes $\frac{c(S_j)}{|S_j \cap X|}$. 
							\State $I \eq I \cup j$.
							\State $X \eq X \setminus S_j$.
						\EndWhile
						\State \Return $I$.
						\EndProcedure
					\end{algorithmic}
				\end{varwidth}%
			}
		\end{center}
	\end{mdframed}

	\item {\bf Analysis.} 
	Suppose the number of loops is $r$, and 
		let's rename the sets such that $S_i$ is the set the algorithm picks in loop $i$. 
	We use $\alg$ to denote $\sum_{i=1}^r c(S_i)$ the cost of the algorithm.
		Let's call the sets picked in the optimum set cover $O_1, \ldots, O_\ell$, and so $\opt = \sum_{j=1}^\ell c(O_j)$.
We use $X_i$ to denote the set of uncovered elements just before loop $i$. Thus, $X_1 = U$ and $X_{r+1} = \emptyset$.
	So,  $S_i \cap X_i$ is the set of elements covered at iteration $i$, and this is precisely $X_i \setminus X_{i+1}$.
	
	\begin{thm}
	 {\sc Weighted Greedy Set Cover} is an $H_n$-approximation algorithm, where $H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$ if the $n$th Harmonic number.
	\end{thm}
\begin{proof}
	Greedy choice tells us for all loops $i\in [r]$, we have
	\begin{equation}\label{eq:greedy-wtd-sc}
		\forall j \in [\ell],~~ \frac{c(S_i)}{|S_i\cap X_i|} ~\leq~\frac{c(O_j)}{|O_j\cap X_i|} 
	\end{equation}
This is because each set $O_j$ was a possible choice in the $i$th loop, but the algorithm picked $S_i$ instead. 

And now we do an ``averaging trick'' which seems pretty slick, but one gets used to it. We use the fact that for any two rational numbers $\frac{a}{b}, \frac{c}{d}$, 
the rational number $\frac{a + c}{b + d}$ is {\em at least} $\min\left(\frac{a}{b}, \frac{c}{d}\right)$. Applying this on the RHS of \eqref{eq:greedy-wtd-sc}, we get that
\begin{equation}
	\forall i\in [r],~~~ \frac{c(S_i)}{|S_i\cap X_i|} ~\leq~\frac{\sum_{j=1}^\ell c(O_j)}{\sum_{j=1}^\ell |O_j\cap X_i|} \le \frac{\opt}{|X_i|} \label{eq:weakness}
\end{equation}
	The last inequality follows since $O_j$'s form a cover and thus, $\bigcup_{j=1}^\ell \left(O_j\cap X_i\right) = X_i$. 
	Taking the $|S_i\cap X_i|$ to the right hand side and 
	adding over all $i$ we get
	\begin{alignat}{4}
		\alg = \sum_{i=1}^r c(S_i)  && ~\underbrace{\le}_{\eqref{eq:weakness}}~ & \opt \cdot \sum_{i=1}^r \frac{|S_i\cap X_i|}{|X_i|} \notag \\
		\qquad && ~\underbrace{=}_{\text{since}~S_i \cap X_i ~=~ X_i \setminus X_{i+1}}~ & \opt \cdot \sum_{i=1}^r \frac{|X_i| - |X_{i+1}|}{|X_i|} \notag \\
		\qquad && ~\le~ & \opt \cdot \left(\frac{1}{|U|} + \frac{1}{|U|-1} + \cdots + 1\right) \label{eq:1}\\							
		\qquad && ~=~ & \opt \cdot H_n \notag
	\end{alignat}
where \eqref{eq:1} is another simple inequality which follows by noticing that the worse case occurs when each new set covers exactly one element. \end{proof}
\exer{\Coffeecup~ Prove~\eqref{eq:1}.}

\item {\bf A Different and Better Analysis.}
	We now show a slightly different way of analyzing the above algorithm which illustrates an analysis tool called the {\em charging trick} in the parlance.
	This analysis also gives a better factor.
	Let $d := \max |S_i|$ be the size of the largest cardinality set in the collection. 
	
	\begin{thm}
		 {\sc Weighted Greedy Set Cover} is an $H_d$-approximation algorithm
	\end{thm}
	\begin{proof}
	Once again let $\{S_1,\ldots,S_r\}$ be the sets picked by the algorithm in that order. Recall that we pick set $S_i$ in iteration $i$ because $\frac{c(S_i)}{|S_i\cap X_i|} \leq \frac{c(S_t)}{|S_t\cap X_i|}$ for any set $S_t$. However, when we pick the set $S_i$ in our solution, the cost increases by $c(S_i)$ and not the ratio. Somehow, we need to argue that although we are locally optimizing for the ratio, we can still upper bound the numerator. 
	
	To this end, we do the following ``charging trick.'' 
	For every element $j \in S_i\cap X_i$, that is, each new element covered by $S_i$, we assign this element a charge $\alpha_j = \frac{c(S_i)}{|S_i\cap X_i|}$. 
	Note that $c(S_i)$, by design, is $\sum_{j\in S_i\cap X_i} \alpha_j$. Now, at the end of the algorithm, every element will be charged once and only once, and furthermore
	\[
	\alg = \sum_{j\in U} \alpha_j
	\]
	
	To see why this is helpful, pick any set $O$ in the input. 
	Suppose $O$ has $d_O \leq d$ elements, and rename them to be $\{1, 2, \ldots, d_O\}$ {\em in the order} in which they were covered
	by the greedy algorithm. This is important.
	
	Now take any element $j\in O$.
	What do we know about $\alpha_j$?
	Well, when this element $j$ was being covered by our algorithm by some set $S_i$ in iteration $i$, we had the choice of picking $O$. Furthermore, by design, at this iteration
	none of the elements in $\{j,j+1,\ldots, d_O\}$ were covered. That is, $\{j, j+1, \ldots, d_O\} \subseteq X_i$, where $X_i$ is the set of uncovered elements at the beginning of this loop.
	Since we picked $S_i$ instead of $O$, we have that the cost-to-new-elements-covered ratio of $S_i$ is at most that of $O$.
	And since the former is the charge on the element $j$, we get
	\begin{equation}\label{eq:dual-fitting}
	\alpha_j \leq \frac{c(O)}{|O\cap X_i|}~\leq\frac{c(O)}{d_O-j+1}~~\underbrace{\Rightarrow}_{\text{summing over $j = 1$ to $d_O$}}~~ \sum_{j\in O} \alpha_j \leq c(O)\cdot H_{d_O} \leq c(O)\cdot H_d
	\end{equation}
	In other words, the charges that the greedy algorithm induces on the elements has the following property : for any set $O$ of the input, the total charge on the elemnts in $O$
	is at most $H_d$ times more than the cost of the set. 
	
	Now, let $\{O_1, \ldots, O_\ell\}$ be the sets picked by the optimal set cover. Using the fact that it is a cover, we can finish the proof of our theorem as follows.
	\[\alg = \sum_{j\in U} \alpha_j ~~\underbrace{\le}_{\text{$O_i$'s form a cover}}~~ \sum_{i=1}^\ell \sum_{j\in O_i} \alpha_j ~~\underbrace{\le}_{\eqref{eq:dual-fitting}}~~ \sum_{i=1}^\ell c(O_i)\cdot H_d = \opt\cdot H_d\]\qedhere
	\end{proof}
\end{itemize}

\subsection*{Notes} The set cover problem is {\em the} classic approximation algorithms problem. 
The analysis of the greedy algorithm is present in the papers~\cite{John1974} by Johnson and~\cite{Lova1975}, while the weighted set cover result
is from the paper~\cite{Chva1979} by Chvatal. On the other hand, obtaining an $(1-\eps)\ln n$-approximation for any constant $\eps > 0$ would imply $P=NP$. These result is present in the papers~\cite{LundY1994},~\cite{Feig1998}, and~\cite{DinurS2014} by Lund and Yannakakis who showed an $\Omega(\ln n)$ hardness, 
Feige who showed this under a stronger complexity theoretic assumption, and Dinur and Steurer, who obtained the final result. See~\cite{Young2008} for a short survey on the set cover problem.

\pagebreak
\bibliographystyle{abbrv}
\bibliography{masterbib}

\end{document}

