\documentclass{llncs} \begin{document} \mainmatter % start of the contributions \title{One for the Price of Two: A Unified Approach\\ for Approximating Covering Problems\\ (Extended Abstract) \thanks{ This research was supported by the fund for the promotion of research at the Technion. } } \author{Reuven Bar-Yehuda} \authorrunning{Reuven Bar-Yehuda} \tocauthor{Reuven Bar-Yehuda (Technion IIT)} % \institute{Computer Science Dept, Tecnion IIT, Haifa 32000, Israel\\ \email{reuven@cs.technion.ac.il},\\ WWW home page: \texttt{http://cs.technion.ac.il/\homedir reuven} } \maketitle % typeset the title of the contribution \begin{abstract} We present a simple and unified approach for developing and analyzing approximation algorithms for covering problems. We illustrate this on approximation algorithms for the following problems: Vertex Cover, Set Cover, Feedback Vertex Set, Generalized Steiner Forest and related problems. The main idea can be phrased as follows: iteratively, pay two dollars (at most) to reduce the total optimum by one dollar (at least), so the rate of payment is no more than twice the rate of the optimum reduction. This implies a total payment (i.e., approximation cost ) $\leq$ twice the optimum cost. Our main contribution is based on a formal definition for covering problems, which includes all the above fundamental problems and others. We further extend the Bafna, Berman and Fujito Local-Ratio theorem. This extension eventually yields a short generic $r$-approximation algorithm which can generate most known approximation algorithms for most covering problems. Another extension of the Local-Ratio theorem to randomized algorithms gives a simple proof of Pitt's randomized approximation for Vertex Cover. Using this approach, we develop a modified greedy algorithm, which for Vertex Cover, gives an expected performance ratio $ \leq 2$. \end{abstract} \noindent{\bf Keywords:} Approximation Algorithm, Local Ratio, Covering Problems, Vertex Cover, Set Cover, Feedback Vertex Set, Generalized Steiner Forest, Randomized Approximations. %---------------------------------------------- \section{Introduction} % \setcounter{theorem}{0}\setcounter{lemma}{0} % \setcounter{equation}{0} Most algorithms for covering problems can be viewed according to two different approaches: the primal-dual principle, and the Local-Ratio principle (see, e.g., recent surveys \cite{Hoc96},\cite{Pas97}). The common characteristic that we find in algorithms for covering problems is the use of vertex weight reductions (or vertex deletion, which is a special case). We are interested in viewing algorithms from the viewpoint of the Local-Ratio theorem \cite{BarEve85}, and its extensions by Bafna, Berman and Fujito \cite{BafBer95}. Following the work of Bafna et al., several studies have shown unified approaches for various families of covering problems. Fujito \cite{Fuj96} gave a generic algorithm for node deletion. Chudack, Goemans, Hochbaum and Williamson \cite{ChuGoe96} united algorithms for the Feedback Vertex Set problem presented by Bafna et al., \cite{BafBer95} and by Becker and Geiger \cite{BecGei94}, using the primal-dual principle. Agrawal, Klein and Ravi \cite{AgrKle91} dealt with the Generalized Steiner Forest problem. Following their work, a couple of generalizations/unifications have recently been done, one by Williamson, Goemans, Mihail, and Vazirani \cite{WilGoe95} and another by Goemans and Williamson \cite{GoeWil95b}. In this work, we try to combine all of these results into a unified definition for covering problems, and present a new local-ratio principle, which explains, with relative ease, the correctness of all the above algorithms. Like the others, we use reductions of the weights in the graph, but we view this in the following way:\\ We try to measure the ``effectiveness'' of the reduction we are making; as a result of the reduction, there may be a change in the optimum. The reduction incurs a cost, and we would like the payment to be bounded by a constant $r$ times the change in the problem's optimum. This principle of ``effectiveness'' can also be viewed in terms of expected values, when the reduction we make is chosen according to some random distribution. This yields an extension of the local-ratio principle in another direction; in this extension, we are interested in bounding the expected change in the optimum as related to the expected cost. This approach gives us a simple proof for Pitt's randomized approximation for Vertex Cover. In addition, we get a new and interesting result: while a deterministic greedy algorithm \cite{Chv79} does not have a constant performance ratio, even for Vertex Cover, a randomized greedy algorithm has a performance ratio of 2. \subsection{Definitions} We are interested in defining a covering problem in such a way that it will contain the following problems: Vertex Cover, Set Cover, Feedback Vertex Set, Generalized Steiner Forest, Min 2-Sat, Min Cut, etc. For a general covering problem, the input is a triple $(X,f:2^X \rightarrow \{0,1\}, \omega:X \rightarrow R^+)$, where $X$ is a finite set, $f$ is monotone, i.e., $A \subseteq B \Rightarrow f(A) \leq f(B)$, and $f(X)=1$. % For a set $C \subseteq X$, we define $\omega(C) = \sum_{x \in C} \omega(x)$, which we call the {\em weight} of $C$. % We say that $C \subseteq X$ is a {\em cover} if $f(C)=1$. The objective of the problem is to find a cover $C^* \subseteq X$ satisfying $$ \omega(C^*)= \min \{\omega(C)| C\subseteq X\ \mbox{and}\ f(C) = 1\}. $$ Such a cover is called an {\em optimum cover}. A cover $C \subseteq X$ is called an {\em $r$-approximation} if $\omega(C) \leq r \cdot \omega(C^*)$, where $C^*$ is an optimum cover. % An algorithm $A$ is called an {\em $r$-approximation} for a family of covering problems if, for every input $(X,f,\omega)$ in the family, $A$ returns a cover which is an $r$-approximation. \subsection{Overview} This paper describes a unified approach for achieving $r$-approximations for covering problems. In Section 2 we describe the general idea of the technique, formalized by the Local-Ratio theorem. In Section 3 we show some applications of this technique to developing algorithms for the Vertex Cover problem. In Section 4 we apply the technique to Set Covering. In Section 5 we present an extension for dealing with randomized approximations. %?In Section 6 we present a linear time 2-approximation algorithm for %?the Min Clique-Complement problem, improving Hochboum's previous %?result \cite{Hoc97}, which was a 4-approximation. In Section 6 we describe an enhancement of the technique which allows us to deal with some recent approximations. In Section 7 we use the enhancement to describe and prove a 2-approximation algorithm for the Feedback Vertex Set problem, in Section 8 we use it for a $2$-approximation for the Generalized Steiner Forest problem, and in Section 9 we present a generic $r$-approximation algorithm which can generate all deterministic algorithms presented in this paper. \section{First Technique: Pay for Every Weight Reduction} % \setcounter{theorem}{0}\setcounter{lemma}{0} % \setcounter{equation}{0} Given a triple $(X,f,\omega)$, our method for achieving an approximation cover is by manipulating the weight function $\omega$. Denote the optimum cover of $(X,f,\omega)$ by OPT$(\omega)$. The following is a fundamental observation for our technique:\\ \noindent {\bf The Decomposition Observation:} For every two weight functions $\omega_1,\omega_2$, $$ \mbox{OPT}(\omega_1)+ \mbox{OPT}(\omega_2) \leq \mbox{OPT} (\omega_1+\omega_2) $$ We select some function $\delta:X \rightarrow R^+$, s.t. $\forall_{x \in X}\ 0 \leq \delta(x) \leq \omega(x)$ The function $\delta$ is used to reduce the weights, giving a new instance $(X,f,\omega-\delta)$. The value of OPT$(\omega-\delta)$ may be smaller than OPT$(\omega)$, and we denote their difference by $\Delta\mbox{OPT} = \mbox{OPT}(\omega) - \mbox{OPT}(\omega-\delta)$. By the Decomposition Observation, $\Delta\mbox{OPT} \geq \mbox{OPT}(\delta)$. This means that by reducing the weights by $\delta$, we reduce the total optimum by at least OPT$(\delta)$. % How much are we willing to pay for this reduction in the optimum? Since our final objective is an $r$-approximation, we would like to pay no more than $r \cdot \mbox{OPT}(\delta)$. Let us be generous and pay for all weight reductions we make, i.e., define $\Delta \mbox{COST}$ to be $\Delta\mbox{COST} = \sum_{x \in X} \delta(x) = \delta(X)$. Therefore, what we need in order to get an $r$-approximation is $$ \delta(X) \leq r \cdot \mbox{OPT}(\delta) $$ or, in the terminology of the title: we are willing to pay no more than $r$ times the gain in optimum reduction. Let us now formalize the technique. Let $(X,f,\omega)$ be a covering problem triple. The function $\delta$ is called $r$-effective if: \begin{enumerate} \item $\forall_{x \in X}\ 0 \leq \delta(x) \leq \omega(x)$ \item $\delta(X) \leq r \cdot \mbox{OPT}(\delta)$. \end{enumerate} Now, consider the following general algorithm:\\ %\vspace*{0.2cm} %========================== \begin{center} \fbox{ \begin{minipage}{8cm} %========================== \noindent{\bf Algorithm $A(X,f,\omega)$} \begin{tabbing} 001\= 002\= 003 \kill \>Select $r$-effective $\delta$\\ \>Call algorithm $B(X,f,\omega-\delta)$ to find a cover $C$ \\ \>Return $C$ \end{tabbing} %========================== \end{minipage} } \end{center} %========================== \begin{theorem} \label{th:c1} {\bf The Local-Ratio Theorem:} \\ If $B$ returns $a$ cover $C$ s.t. $(\omega - \delta)(C) \leq r \cdot \mbox{OPT}(\omega-\delta)$\\ then $\omega(C) \leq r \cdot \mbox{OPT}(\omega)$ \end{theorem} %\noindent{\bf Proof.} \begin{proof} $\omega(C)$=\\ %\vspace*{0.2cm} \begin{tabular}{rll} %$\omega(C)$ &$=(\omega-\delta)(C) + \delta(C)$ & [linearity of $\omega$ and $\delta$]\\ &$\leq (\omega-\delta)(C) + \delta(X)$ & [$\delta(C) \leq \delta(X)$]\\ &$\leq r \cdot \mbox{OPT}(\omega-\delta) + r \cdot \mbox{OPT}(\delta)$ & [$B$'s property and the $r$-effectiveness of $\delta$]\\ &$\leq r \cdot \mbox{OPT}(\omega)$& [Decomposition Observation] \end{tabular} \qed \end{proof} %\hfill $\Box$ \\ This is illustrated in the next section by a sequence of 2-approximation algorithms for the Vertex Cover problem. %\newpage \section{The Vertex Cover Problem} % \setcounter{theorem}{0}\setcounter{lemma}{0} % \setcounter{equation}{0} Let $G=(V,E)$ be a simple graph with vertices $V$ and edges $E \subseteq V^2$. The {\em degree} of a vertex $v \in V$ is defined by $d(v) = |\{e \in E:v \in e\}|$. The {\em maximum vertex degree} is defined by $\Delta_v = \max\{d(v):v \in V\}$. A set $C \subseteq V$ is called a {\em vertex cover} of $G=(V,E)$ if every edge has at least one endpoint in $C$, i.e., $\forall_{e \in E}\ e \cap C \neq \phi$. The Vertex Cover problem (VC) is: given a simple graph $G = (V,E)$ and a weight $\omega(v) \geq 0$ for each $v \in V$, find a vertex cover $C$ with minimum total weight. The Vertex Cover problem (VC) is NP-hard even for planar cubic graphs with unit weight \cite{GarJoh79}. For unit-weight Vertex Cover, Gavril (see \cite{GarJoh79}) suggested a linear time 2-approximation algorithm. For the general Vertex Cover problem, Nemauser and Trotter \cite{NemTro75} developed a local optima algorithm that implies a 2-approximation, see \cite{Hoc80}, \cite{Hoc83}, \cite{Hoc96}. Until today, the best ratio known is 2. The first linear time algorithm was found by Bar-Yehuda and Even \cite{BarEve81}. Their proof uses the primal-dual approach. It took a few more years to find a different kind of proof -- the local-ratio theorem \cite{BarEve85}. \subsection{Bar-Yehuda \& Even's 2-Approximation Algorithm} The main idea is as follows: let $\{x,y\} \in E$, and let $\epsilon = \min(\omega(x), \omega(y))$. Reducing $\omega(x)$ and $\omega(y)$ by $\epsilon$ has $\Delta\mbox{COST} = 2 \epsilon$ while $\Delta\mbox{OPT} \geq \epsilon$, since one of the two vertices $x,y$ participates in any optimum. So we pay $2\epsilon$ in order to reduce the total optimum by at least $\epsilon$, repeating this process until the optimum reaches zero. The total cost will be no more than twice the optimum. Therefore, the 2-effective $\delta$ selected is $$ \delta(v) = \left \{\begin{array}{ll} \epsilon & v \in\{x,y\}\\ 0 & \mbox{else} \end{array} \right. $$ %========================== \begin{center} \fbox{ \begin{minipage}{8cm} %========================== \noindent{\bf Algorithm BarEven$(G=(V,E),\omega)$} \begin{tabbing} 001\=002\=003\=004\=005 \kill \> For each $e \in E$\\ \> \> Let $\epsilon = \min \{\omega(v)|v \in e\}$\\ \> \> For each $v \in e$\\ \> \> \> $\omega(v) = \omega(v) - \epsilon$\\ \> Return $C=\{v:\omega(v)=0\}$ \end{tabbing} %========================== \end{minipage} } \end{center} %========================== \begin{theorem} \label{th:c2} Algorithm BarEven is a 2-approximation. \end{theorem} \begin{proof} By induction on $|E|$. The first step uses $\delta$, which is 2-effective, since OPT$(\delta) = \epsilon$ and $\delta(V) = 2 \epsilon$. The remaining steps perform a 2-approximation for $(G, \omega-\delta)$, by the induction hypothesis, and the Local Ratio Theorem. \\ \qed \end{proof} For primal-dual proof see \cite{BarEve81}. For first local-ratio proof, see \cite{BarEve85}. %\noindent{\bf Remarks.} %\begin{enumerate} %\item %For a given $(G,\omega)$, select a function $f:E \rightarrow R^+$, and %define %\[\delta(v) = \sum_{v \in e} f(e) \;\;\;.\] %From the above it is obvious that if $\forall_v \ \delta(v) \leq %\omega(v)$ then $\delta$ is 2-effective. % % %\item The algorithm of Gavril (see \cite{GarJoh79}) can be viewed in %terms of remark 1: select a maximal matching $M$ and define $f(e)=1$ if %$e \in M$ and $f(e) = 0$ otherwise. % %\item Gonzales \cite{Gon95} combined the ideas of Gavril's algorithm and %Algorithm BarEven. He extended the definition of a maximal matching: %given $(G,\omega)$, a matching is a function $f:E \rightarrow R^+$ which %satisfies %\begin{equation} %\label{eqn:1} %\sum_{v \in e} f(e) \leq \omega(v) %\end{equation} %for every vertex $v$. A matching is maximal if each edge has a saturated %endpoint $v$ (i.e., $v$ satisfies equation~\ref{eqn:1} with equality). %If we define %$\delta$ as in remark 1, we get a 2-effective function. Clearly, the set %of saturated vertices is a cover, so this cover is a 2-approximation. % %This ``global'' approach of Gonzales can be explained in terms of the %local approach: %define $f(e) = \epsilon_e$, where $\epsilon_e$ is the value $\epsilon$ %subtracted from the two endpoints of $e$ in Algorithm BarEven. % %\end{enumerate} \subsection{Clarkson's Greedy Modification} Clarkson \cite{Cla83} uses the primal-dual approach to get the following 2-approximation algorithm.\\ %========================== \begin{center} \fbox{ \begin{minipage}{8cm} %========================== \noindent{\bf Algorithm Clarkson $(G=(V,E),\omega)$} \begin{tabbing} 001\=002\=003\=004\=005 \kill \> $C=\phi$\\ \> While $E \neq \phi$\\ \> \> Let $x \in V$ with minimum $\epsilon = \frac{\omega(x)}{d(x)}$\\ \> \> For each $y \in \Gamma(x)$ (the neighbors of $x$)\\ \> \> \> $\omega(y) = \omega(y) - \epsilon$\\ \> \> Add $x$ to $C$ and remove it from $G$\\ \> Return $C$ \end{tabbing} %========================== \end{minipage} } \end{center} %========================== \begin{theorem} \label{th:c3} Clarkson's Algorithm is a 2-approximation. \end{theorem} \begin{proof} The $\delta$ that the algorithm chooses is $\delta(x) = \omega(x)$, $\delta(y) = \frac{\omega(x)}{d(x)}$ for every $y \in \Gamma(x)$, and 0 for all others. We need to show that $\delta$ is 2-effective, i.e. (1) $\forall_{v \in V} \ \delta(v) \leq \omega(v)$ (2)~$\delta(V) \leq 2 \cdot \mbox{OPT}(\delta)$. \begin{enumerate} \item for $v = x$ we defined $\delta(x) = \omega(x)$. For $v \in \Gamma(x)$, we defined $\delta(v) = \frac{\omega(x)}{d(x)} \leq \frac{\omega(v)}{d(v)}\leq \omega(v)$. For all others, $\delta(v) = 0 \leq \omega(v)$. \item $\delta(V) = \delta(x) + \delta(\Gamma(x)) + \delta(V - \{x\} - \Gamma(x)) = \omega(x) + \omega(x) +0 = 2 \cdot \omega(x) = 2 \cdot \mbox{OPT}(\delta)$ \end{enumerate} %$\Delta\mbox{OPT} \geq \mbox{OPT}(\delta) %= \min(\delta(x), \delta(\Gamma(x)) = %\omega(x)$, while $\Delta\mbox{COST} = \delta (\{x\} \cup %\Gamma(x)) = 2 \cdot \omega(x)$. The rest of the proof is by induction, using the Local Ratio Theorem.\\ \qed \end{proof} %\noindent{\bf Remarks.} %\begin{enumerate} %\item The main step of Clarkson's algorithm can be %rewritten as %\begin{tabbing} %001\= 002\= \kill %For each $(x,y)$ s.t. $y \in \Gamma(x)$\\ %\> $\omega(x) = \omega(x) - \epsilon$\\ %\> $\omega(y) = \omega(y) -\epsilon$ %\end{tabbing} %and therefore it is a special case of the previous %approach. %\item Clarkson chooses to subtract exactly the same amount %from all the neighbors. %The correctness of the algorithm needs only that %$\delta(\Gamma(x)) = \omega(x)$. The freedom to %distribute the subtraction differently may be used %to add additional heuristic criteria. %\item See also the work of Gusfield and Pitt \cite{GusPit86} for another %interesting interpretation of the BarEven and Clarkson algorithms. %\end{enumerate} \subsection{Subgraph Removal} Suppose we are given a family of graphs for which we wish to develop a 1.5-approximation. Getting rid of triangles is ``free''. To get rid of a triangle, say $x,y,z$, with weights $\epsilon = \omega(x) \leq \omega(y) \leq \omega(z)$, define $\delta(x) = \delta(y) = \delta(z) = \epsilon$, and $\forall_{v \not \in \{x,y,z\}}$ $\delta(v) = 0$. Obviously, OPT$(\delta)=2 \epsilon$, while $\delta(\{x,y,z\})=3 \epsilon$, and therefore $\delta$ is 1.5-effective. This was helpful, for example, in developing an efficient 1.5-approximation for planar graphs, see \cite{BarEve85} and \cite{Hoc83}. The $(2-\log\log n/(2 \log n))$ - approximation algorithm \cite{BarEve85} uses this approach to ``get rid'' of odd cycles of length $\leq 2k-1$, where $k \approx 2 \log n/\log \log n$. Let $C \subseteq V$ be a cycle of length $2k-1$. Generalizing the idea for triangles, let $\epsilon = \min\{\omega(v):v \in C\}$, and define $\delta(v) = \epsilon$ if $v \in C$, and 0 otherwise. In this case, $\delta(C) / \mbox{OPT}(\delta) \leq (2k-1)/k=2-\frac{1}{k}$. Bar-Yehuda and Even's linear time algorithm for VC can also be viewed as a subgraph removal algorithm, where the subgraph removed each time is an edge. \section{Vertex Cover in Hypergraphs} % \setcounter{theorem}{0}\setcounter{lemma}{0} % \setcounter{equation}{0} Let $G=(V,E)$ be a simple\footnote{A hypergraph is called simple if no edge is a subset of another edge.} hypergraph with vertices $V$ and edges $E \subseteq 2^V$. The {\em degree of a vertex} $v \in V$ is defined by $d(v) = |\{e \in E:v \in e\}|$. The {\em maximum vertex degree} is defined by $\Delta_v = \max\{d(v):v \in V\}$. The {\em degree of an edge} $e \in E$ is defined by $d(e) = |e|$. The {\em maximum edge degree} is defined by $\Delta_e=\max\{|e|:e \in E\}$. A set $C \subseteq V$ is called a {\em vertex cover} of $G=(V,E)$ if every edge $e \in E$ has at least one endpoint in $C$ (i.e., $e \cap C \neq \phi$). The Hypergraph Vertex Cover problem (HVC) is: given $G=(V,E)$, and for each $v \in V$ a weight $\omega(v) \geq 0$, find a cover with minimum total weight. This generalization of the VC problem is exactly the Set Covering problem (SC). Algorithm BarEven is written in hypergraph terminology, and therefore approximates HVC as well. \begin{theorem}\label{th:d1} Algorithm BarEven is a $\Delta_e$-approximation for HVC. \end{theorem} \begin{proof} For $e \in E, \epsilon = \min\{\omega(v):v \in e\}$. Define $\delta(v) = \epsilon$ for all $v \in e$ and 0 otherwise. Since OPT$(\delta) = \epsilon$ and $\delta(V) = \delta(e) = |e| \cdot \epsilon \leq \Delta_e \cdot \epsilon$, this implies that $\delta$ is $\Delta_e$-effective.\\ \qed \end{proof} %\noindent{\bf Remarks.} %\begin{enumerate} %\item Hochbaum \cite{Hoc80} was the first to show a %polynomial time $(O(n^3))\ \Delta_e$-approximation %algorithm. %\item Chvatal \cite{Chv79} showed that a greedy %algorithm is a $ln \Delta_v$-approximation %algorithm. %\item %The Hypergraph Vertex Cover %problem can be further generalized. For many such %generalizations, the above approach works. For %example, the k-HVC problem demands that each edge %$e$ have at least $k$ endpoints in the cover $C$ %(i.e., $|C \cap e|\geq k$). In this case, Algorithm BarEven is a %$\frac{\Delta_e}{k}$-approximation, since OPT$(\delta)$ is %$k \epsilon$ and not $\epsilon$. %\end{enumerate} %\newpage \section{Randomized $r$-approximations} %\setcounter{theorem}{0} %\setcounter{equation}{0} Let us select $\delta:X \rightarrow R^+$ from some random distribution. Such a random distribution is called $r$-effective if \begin{enumerate} \item $\forall_{x \in X}\ 0 \leq \delta(X) \leq \omega(x)$ and \item $Exp[\delta(X)] \leq r \cdot Exp[\mbox{OPT}(\delta)]$ \end{enumerate} Intuitively: the randomized rate of payment is no more than $r$ times the randomized rate of the optimum reduction. Now consider the following general algorithm: %\newpage %========================== \begin{center} \fbox{ \begin{minipage}{8cm} %========================== \noindent{\bf Algorithm $A(X,f,\omega)$} \begin{tabbing} 001\= 002\= 003\= \kill \> Select $\delta:X \rightarrow R^+$ from some $r$-effective random distribution\\ \> Call algorithm $B(X,f,\omega-\delta)$ to find a cover $C$\\ \> Return $C$ \end{tabbing} %========================== \end{minipage} } \end{center} %========================== \begin{theorem} \label{th:e1} {\bf The Randomized Local-Ratio Theorem:}\\ If $B$ returns a cover $C$ s.t. $Exp[(\omega-\delta)(C)] \leq r \cdot Exp[\mbox{OPT}(\omega-\delta)]$, \\ then $Exp[\omega(C)] \leq r \cdot \mbox{OPT}(\omega)$. \end{theorem} \begin{proof} $Exp[\omega(C)]=$\\ %\vspace*{0.2cm} \begin{tabular}{lll} & $= Exp[(\omega-\delta)(C)] + Exp[\delta(C)]$\\ &$\leq r \cdot Exp[\mbox{OPT}(\omega-\delta)] + r \cdot Exp[\mbox{OPT}(\delta)]$& [from the properties of $B$ and \\ & & of the distribution ]\\ &$= r \cdot Exp[\mbox{OPT}(\omega-\delta)+\mbox{OPT}(\delta)]$\\ &$\leq r \cdot Exp[\mbox{OPT}(\omega)]$ &[by the Decomposition Observation.]\\ &$= r \cdot \mbox{OPT}(\omega)$. \end{tabular} %\vspace{0.2cm} \qed \end{proof} An algorithm $A$ that produces a cover $C$ satisfying $Exp[\omega(C)] \leq r \cdot \mbox{OPT}(\omega)$ is called a {\em randomized-$r$-approximation}. \subsection{Pitt's Randomized-2-Approximation Algorithm} %========================== \begin{center} \fbox{ \begin{minipage}{8cm} %========================== \noindent{\bf Algorithm Pitt $(G=(V,E),\omega)$} \begin{tabbing} 001\= 002\= 003\= \kill \> $C= \{x:\omega(x)=0\}$ and delete $C$ from $G$\\ \> While $E \not = \phi$\\ \> \> Select $e \in E$\\ \> \> Let $\bar{\omega}=\frac{1}{\sum_{x \in e} \frac{1}{\omega(x)}}$\\ \>\> Select at random $x \in e$ with $Prob(x) = \frac{\bar{\omega}}{\omega(x)}$\\ \> \> Remove $x$ from $G$ and add it to $C$\\ \> Return $C$ \end{tabbing} %========================== \end{minipage} } \end{center} %========================== Pitt \cite{Pit84} uses the primal-dual approach to prove that his algorithm is a randomized-2-approximation algorithm for Vertex Cover. Using our technique, we get: \begin{theorem} \label{th:e2} Pitt's algorithm is a randomized-$\Delta_e$-approximation for HVC. \end{theorem} \begin{proof} To prove correctness, we use the Randomized Local-Ratio theorem. We can regard the selection of a vertex $x$ and its removal as if we defined $\delta(x) = \omega(x)$, and $\forall_{y \not = x}$ $\delta(y)=0$. We show that in each iteration, the distribution is $\Delta_e$-effective. For this, we need to show that $Exp[\delta(V)] \leq r \cdot Exp[\mbox{OPT}(\delta)]$. Let $e$ be the edge chosen in the first iteration, and let $C^*$ be an optimum cover. $$ Exp[\mbox{OPT}(\delta)] = Exp[\delta(C^*)] = \sum_{x \in e \cap C^*} p(x) \cdot \omega(x) $$ $$ = \sum_{x \in e \cap C^*}\frac{\bar{\omega}} {\omega(x)}\cdot \omega(x) = \bar{\omega} \cdot |e \cap C^*| \geq \bar{\omega} $$ $$ Exp[\delta(V)] = \sum_{x \in V} p(x) \cdot \omega(x) = \sum_{x \in e} \frac{\bar{\omega}}{\omega(x)} \cdot \omega(x) = \bar{\omega} \cdot |e| \leq \bar{\omega} \cdot \Delta_e $$ \qed \end{proof} \subsection{Our Modified Greedy Algorithm} The greedy algorithm for set cover \cite{Chv79} is a $ln \Delta_v$-approximation. Algorithm BarEven is a $\Delta_e$-approximation. In some families of problems (e.g., VC), $\Delta_e$ is preferable to $ln \Delta_v$. In these cases, we would like to have a ratio of $\Delta_e$, but we may also prefer to use the ``greedy'' heuristic. Can we have the best of both worlds? As we have seen, this is possible: Clarkson's modified greedy algorithms for VC can easily be modified for HVC, using the Local-Ratio theorem. But, even for unit-weight Vertex Cover, it may have a problem with robustness, due to error accumulation. The following randomized greedy modification does not ``reduce weights'', but rather deletes vertices: %\newpage %========================== \begin{center} \fbox{ \begin{minipage}{8cm} %========================== \noindent{\bf Algorithm Random-Greedy $(G=(V,E),\omega)$} \begin{tabbing} 001\= 002\= 003\= \kill \> $C= \{x:\omega(x)=0\}$ and delete $C$ from $G$\\ \> While $ E \neq \phi$\\ \> \> Let $\bar{\omega}=\frac{1}{\sum_{x \in V}\frac{d(x)}{\omega(x)}}$ \\ \> \> Select at random $x \in V$ with $Prob(x)=\frac{d(x)}{\omega(x)} \cdot \bar{\omega}$\\ \> \> Remove $x$ from $G$ and add it to $C$\\ \> Return $C$ \end{tabbing} %========================== \end{minipage} } \end{center} %========================== Let $C^*$ be an optimum cover, $$ Exp[\mbox{OPT}(\delta)] = Exp[\delta(C^*)] = \sum_{x \in C^*} p(x) \cdot \omega(x) = \sum_{x \in C^*} d(x) \cdot \bar{\omega} \geq |E| \cdot \bar{\omega} $$ $$ Exp[\delta(V)] = \sum_{x \in V} p(x) \cdot \omega(x) = \sum_{x \in V} d(x) \cdot \bar{\omega} \leq \Delta_e \cdot |E| \cdot \bar{\omega} $$ this implies: \begin{theorem} \label{th:e3} Random-Greedy is a randomized-$\Delta_e$-approximation for the HVC problem. \end{theorem} \begin{corollary} Random-Greedy is a randomized-2-approximation for VC. \end{corollary} \section{Pay Only for Minimal Covers} %\setcounter{theorem}{0} %\setcounter{equation}{0} Following Bafna, Berman and Fujito \cite{BafBer95}, we extend the Local-Ratio theorem. This will be shown to be useful in the following sections. In the previous analyses, we used $\delta(V)$ as an upper bound for the payment in a step. This may be too much. If we knew the final cover $C$ eventually found by the algorithm, we would know that $\delta(C)$ is the exact payment. In practice, we can restrict the final cover $C$ to be a minimal cover. Defined formally: \\ \noindent {\bf Definition} A cover $C$ is a {\em minimal cover} if $\forall_{x \in c}\ C\backslash\{x\}$ is not a cover. A cover $C$ is a {\em minimal cover} {\em w.r.t a weight function $\omega$}, if $\forall_{x \in C\ \mbox{and}\ \omega(x)>0} C\backslash \{x\}$ is not a cover. If we know that the final cover $C$ is minimal w.r.t. $\delta$, we can bound the payment $\Delta$COST by $\max\{\delta(C)|C\ \mbox{is\ minimal\ w.r.t}\ \delta\}$. Define $\delta:X \rightarrow R^+$ to be {\em minimal-$r$-effective} if \begin{enumerate} \item $\forall_{x \in X}\ 0 \leq \delta(X) \leq \omega(x)$ \item $\delta(C) \leq r \cdot \mbox{OPT}(\omega)$ for all $C$ that are minimal w.r.t. $\delta$. \end{enumerate} Consider the following general algorithm $A$: \vspace*{0.2cm} %========================== \begin{center} \fbox{ \begin{minipage}{8cm} %========================== \noindent{\bf Algorithm $A(X,f,\omega)$} \begin{tabbing} 001\= 002\= 003\= 004\= 005\= 006\= 007\= \kill \>Select a minimal-$r$-effective $\delta$\\ \>Call algorithm $B(X,f,\omega-\delta)$ to find a cover $C$ \\ \>{\bf Removal loop:}\\ \>for each $x \in C$, if $\delta(x) > 0$ and $C \setminus \{x\}$ is a cover then $C = C \setminus \{x\}$ \\ \>Return $C$ \end{tabbing} %========================== \end{minipage} } \end{center} %========================== \begin{theorem} \label{th:e4} {\bf The Extended Local-Ratio Theorem}\\ If $B$ returns a cover $C$ s.t. $ (\omega-\delta)(C) \leq r \cdot \mbox{OPT}(\omega-\delta)$, then $\omega(C) \leq r \cdot \mbox{OPT}(\omega)$. \end{theorem} \begin{proof} After the ``removal loop'', $C$ is still a cover, but it is also minimal w.r.t. $\delta$, and therefore $\delta(C) \leq r \cdot \mbox{OPT}(\delta)$. Hence \vspace*{0.2cm} \begin{tabular}{lll} $\omega(C)$& $= (\omega-\delta)(C)+\delta(C)$ & \\ & $\leq r \cdot \mbox{OPT}(\omega-\delta) + r \cdot \mbox{OPT}(\delta)$ & [by the properties of $B$ and $\delta$]\\ & $\leq r \cdot \mbox{OPT}(\omega)$ &[by the Decomposition Observation] \end{tabular} \qed \vspace{0.2cm} \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%add \section{The Feedback Vertex Set Problem} %\setcounter{theorem}{0} %\setcounter{equation}{0} Let $G=(V,E)$ be a simple graph with weight function $\omega:V \rightarrow R^+$. A set $F \subseteq V$ is called a Feedback Vertex Set (FVS) if $G \backslash F$ is a forest, i.e., for every cycle $C \subseteq V,\ C \cap F \neq \phi$. The FVS problem is: given a graph $G=(V,E)$ and a weight function $\omega:V \rightarrow R^+$, find a FVS, $F$, with minimum total weight. The FVS problem is NP-hard \cite{GarJoh79}. Furthermore, any $r$-approximation for FVS implies an $r$-approximation with the same time complexity for the VC problem (each edge in the VC instance graph can be replaced by some cycle). This implies that a $2$-approximation is the best we can hope for, as long as the ratio for VC is not improved. The first non-trivial approximation algorithm was given by Bar-Yehuda, Geiger, Naor and Roth \cite{BarGei97}. They present a 4-approximation for unit weights and an $O(\log n)$-approximation for the general problem. Following their paper, Bafna, Berman and Fujito \cite{BafBer95} found the first $2$-approximation. They were also the first to generalize the local ratio theorem to deal with ``paying'' according to a minimal cover. Their approach has helped to deepen our understanding of approximations for covering problems. Following their approach, Becker and Geiger \cite{BecGei94} present a relatively simple $2$-approximation. Following all these, Chudak, Goemans, Hochbaum and Williamson \cite{ChuGoe96} explained all of these algorithms in terms of the primal-dual method. They also gave a new $2$-approximation algorithm, which is a simplification of the Bafna et al. algorithm. Using the Extended Local Ratio theorem, we can further simplify the presentation and proof of all these three algorithms, \cite{BafBer95}, \cite{ChuGoe96}, \cite{BecGei94}. Let us illustrate this for the Becker-Geiger algorithm.\\ %\noindent{\bf Remark:} All three algorithms use some %backtracking in order to preserve the minimal cover %property. We find it simpler to represent this %recursively. The main idea behind Becker and Geiger's algorithm is the weighted graph we call a degree-weighted graph. A {\em degree-weighted graph} is a pair $(G,\omega)$ s.t. each vertex $v$ has a weight $\omega(v)=d(v) > 1$. \begin{theorem}\label{th:g1} Every minimal FVS in a degree-weighted graph is a 2-approximation. \end{theorem} \begin{proof} Let $C$ be a minimal cover, and $C^*$ an optimum cover. We need to prove $\omega(C) \leq 2 \cdot \omega (C^*)$. It is enough to show that $$ \sum_{x \in C} \omega(x) \leq 2 \cdot \sum_{x \in C^*} \omega (x) $$ by definition, it is enough to show that $$ \sum_{x \in C} d(x) \leq 2 \cdot \sum_{x \in C^*} d(x). $$ This is proved in \cite{BecGei94}. A simple proof also appears in \cite{ChuGoe96}.\\ \qed \end{proof} \begin{corollary} \label{co:co2} If $G=(V,E)$ is a graph with $\forall_{v \in V}\ d(v) > 1$, and $\delta:V \rightarrow R^+$ satisfies $\forall_{v \in V}\ 0 \leq \delta(v) = \epsilon \cdot d(v) \leq \omega(v)$ for some $\epsilon$, then $\delta$ is 2-effective. \end{corollary} \begin{proof} We need only show that for every minimal cover $C,\ \delta(C) \leq 2 \cdot \mbox{OPT}(\delta)$. This is immediate from Theorem \ref{th:g1}.\\ \qed \end{proof} In order to guarantee termination, we choose $\epsilon = \min_{v \in V} \frac{\omega(v)}{d(v)}$.\\ \vspace*{0.2cm} %========================== \begin{center} \fbox{ \begin{minipage}{8cm} %========================== \noindent{\bf Algorithm BeckerGeiger $(G=(V,E),\omega)$} \begin{tabbing} 001\= 002\= 003\= \kill \> If $G$ is a tree return $\phi$\\ \> If $\exists_{x \in V}\ d(x) \leq 1$ return BeckerGeiger$(G \backslash \{x\}, \omega)$\\ \> If $\exists_{x \in V}\ w(x) = 0$ return $\{x\}+$BeckerGeiger$(G \backslash \{x\}, \omega)$\\ \> Let $\epsilon = \min_{v \in V} \frac{\omega(v)}{d(v)}$\\ \> Define $\delta : \forall_{x \in V}\ \delta(x) = \epsilon \cdot d(x)$\\ \> $C = $ BeckerGeiger$(G,\omega-\delta)$\\ \> {\bf Removal loop:}\\ \>for each $x \in C$, if $\delta(x) > 0$ and $C\backslash \{x\}$ is a cover then $C=C\backslash\{x\}$ \end{tabbing} %========================== \end{minipage} } \end{center} %========================== \begin{theorem} \label{th:g2} Algorithm BeckerGeiger is a 2-approximation for FVC. \end{theorem} \begin{proof} The algorithm terminates, since in each recursive call, at least one more vertex weight becomes zero. Therefore we can use induction. The base of induction is trivial. Let us assume inductively that the recursive call returns $C$ s.t. $$ (\omega-\delta)(C) \leq 2 \cdot \mbox{OPT} (\omega-\delta). $$ Since, by Corollary \ref{co:co2}, $\delta$ is 2-effective, we can use the Extended Local-Ratio theorem to conclude that $\omega(C) \leq 2 \cdot \mbox{OPT} (\omega)$.\\ \qed \end{proof} \section{Generalized Steiner Forest and Related Problems} %\setcounter{theorem}{0} %\setcounter{equation}{0} Goemans and Williamson \cite{GoeWil95b} have recently presented a general approximation technique for covering cuts of vertices with edges. Their framework includes the Shortest Path, Minimum-cost Spanning Tree, Minimum-weight Perfect Matching, Traveling Salesman, and Generalized Steiner Forest problems. All these problems are called Constraint Forest Problems. To simplify the presentation, let us choose the Generalized Steiner Forest problem. We are given a graph $G=(V,E)$, a weight function $\omega:E \rightarrow R^+$, and a collection of terminal sets $T = \{T_1, T_2, \ldots , T_t\}$, each a subset of $V$. A subset of edges $C \subseteq E$ is called a Steiner-cover if, for each $T_i$, and for every pair of terminals $x,y \in T_i$, there exists a path in $C$ connecting $x$ to $y$. The Generalized Steiner Forest problem is: given a triple $(G,T, \omega)$, find a Steiner-cover $C$ with minimum total weight $\omega(C)$. In order to get a 2-effective weight function, let us define an edge-degree-weighted graph. An {\em edge-degree-weighted graph} is a triple $(G,T,\omega)$ s.t. \[\forall_{e \in E}\ \omega(e) = d_T(e) = |\{x \in e : \exists_i \ x \in T_i \}| \;\;\;.\] \begin{theorem}\label{th:h1} Every minimal cover in an edge-degree-weighted graph is a 2-approximation. \end{theorem} \begin{proof} The proof is an elementary exercise, see, e.g., \cite{GoeWil96}.\\ \qed \end{proof} So now, given $(G,T,\omega)$, we can easily compute a 2-effective weight function $\delta(e) = d_T(e) \cdot \epsilon$ for all $e \in E$, and in order to guarantee termination, we select $\epsilon = \min\{\omega(e) / d_T(e) |d_T(e) \neq 0\}$. Now we can proceed as follows:\\ ``Shrink'' all pairs $e=\{x, y\}$ s.t. $(\omega-\delta)(e)=0$. Recursively, find a minimal 2-approximation Steiner-cover, $C$. Add all ``shrunken'' edges to the cover $C$. In order to guarantee the minimality property, apply the following removal loop: \begin{tabbing} 001\= 002\= 003\= \kill \>For each ``shrunken'' edge $e$ do: if $C \setminus \{x\}$ is a Steiner-cover, delete $e$ from $C$ \end{tabbing} \section{A Generic $r$-Approximation Algorithm} We now present a generic $r$-approximation algorithm that can be used to generate all the deterministic algorithms presented in this paper. The weight function $\delta$ is called $\omega$-tight if $\exists_{x \in X}\ \delta(x) = \omega(x) > 0$.\\ \vspace*{0.2cm} %========================== \begin{center} \fbox{ \begin{minipage}{8cm} %========================== \noindent{\bf Algorithm Cover $(X,f,\omega)$} \begin{tabbing} 001\= 002\= 003\= \kill \>If the set $\{x \in X:\omega(x)=0\}$ is a cover then return this set.\\ \> Select $\omega$-tight minimal-$r$-effective $\delta:X \rightarrow R^+$\\ \>Recursively call Cover $(X,f,\omega-\delta)$ to get a cover $C$\\ \> {\bf Removal loop:}\\ \>for each $x \in C$, if $\delta(x) > 0$ and $C \backslash\{x\}$ is a cover then $C=C\backslash\{x\}$ \end{tabbing} %========================== \end{minipage} } \end{center} %========================== \begin{theorem} \label{th:e5} Algorithm Cover is an $r$-approximation. \end{theorem} \begin{proof} Define $X^+ = \{x \in X| \omega (x) > 0\}$. Since $\delta$ is $\omega$-tight, the size of $X^+$ decreases at each recursive call. This implies that the total number of recursive calls is bounded by $|X|$. We can now prove the theorem using induction on $|X^+|$.\\ \noindent{\bf Basis:} $|X^+|=0$, hence $\omega(X) = 0$.\\ \noindent{\bf Step:} We can consider the recursive call as the algorithm $B$ in the Extended Local-Ratio theorem, theorem \ref{th:e4}. By the induction hypothesis, this recursive call, Cover $(X,f,\omega-\delta)$, satisfies $B$'s requirement in the theorem, i.e., $(\omega-\delta)(X) \leq r \cdot \mbox{OPT}(\omega-\delta)$. Since $\delta$ is minimal-$r$-effective, it remains to show that $C$ is a minimal cover w.r.t $\delta$. This follows from the last step of algorithm Cover.\\ \qed \end{proof} \noindent{\bf Acknowledgment}\\ We would like to thank Yishay Rabinovitch and Joseph Naor for helpful discussions, Avigail Orni for her careful reading and suggestions, and Yvonne Sagi for typing. \begin{thebibliography}{10} \bibitem{AgrKle91} A.~Agrawal, P.~Klein, and R.~Ravi. \newblock When trees collide: an approximation algorithm for the generalized steiner problem in networks. \newblock {\em Proc. 23rd ACM Symp. on Theory of Computing}, pages 134--144, 1991. \bibitem{BafBer95} V.~Bafna, P.~Berman, and T.~Fujito. \newblock Constant ratio approximation of the weighted feedback vertex set problem for undirected graphs. \newblock {\em ISAAC '95 Algorithms and Computation}, (1004):142--151, 1995. \bibitem{BarEve81} R.~Bar-Yehuda and S.~Even. \newblock A linear time approximation algorithm for the weighted vertex cover problem. \newblock {\em Journal of Algorithms}, 2:198--203, 1981. \bibitem{BarEve85} R.~Bar-Yehuda and S.~Even. \newblock A local-ratio theorem for approximating the weighted vertex cover problem. \newblock {\em Annals of Discrete Mathematics}, 25:27--46, 1985. \bibitem{BarGei97} R.~Bar-Yehuda, D.~Geiger, J.~Naor, and R.~Roth. \newblock Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and bayesian inference. \newblock {\em Accepted to SIAM J. on Computing}, 1997. \bibitem{BecGei94} A.~Becker and D.~Geiger. \newblock Approximation algorithms for the loop cutset problem. \newblock {\em Proc. 10th Conf. on Uncertainty in Artificial Intelligence}, pages 60--68, 1994. \bibitem{ChuGoe96} F.~Chudak, M.~Goemans, D.~Hochbaum, and D.~Williamson. \newblock A primal-dual interpretation of recent 2-approximation algorithms for the feedback vertex set problem in undirected graphs. \newblock {\em Unpublished}, 1996. \bibitem{Chv79} V.~Chvatal. \newblock A greedy heuristic for the set-covering problem. \newblock {\em Math. of Oper. Res.}, 4(3):233--235, 1979. \bibitem{Cla83} K.~Clarkson. \newblock A modification of the greedy algorithm for the vertex cover. \newblock {\em Info. Proc. Lett.}, 16:23--25, 1983. \bibitem{Fuj96} T.~Fujito. \newblock A unified local ratio approximation of node-deletion problems. \newblock {\em ESA, Barcelona, Spain}, pages 167--178, September 1996. \bibitem{GarJoh79} M.~Garey and D.~Johnson. \newblock {\em Computers and Intractability}. \newblock W.H. Freeman, 1979. \bibitem{GoeWil95b} M.~Goemans and D.~Williamson. \newblock A general approximation technique for constrained forest problems. \newblock {\em SIAM Journal on Computing}, 24(2):296--317, 1995. \bibitem{GoeWil96} M.~Goemans and D.~Williamson. \newblock The primal-dual method for approximation algorithms and its application to network design problems. \newblock {\em Approximation Algorithms for NP-Hard Problems}, 4, 1996. \bibitem{Hoc80} D.~Hochbaum. \newblock Approximation algorithms for the set covering and vertex cover problems. \newblock {\em SIAM J. Comput.}, 11(3):555--556, 1980. \bibitem{Hoc83} D.~Hochbaum. \newblock Efficient bounds for the stable set, vertex cover and set packing problems. \newblock {\em Discrete Applied Mathematics}, 6:243--254, 1983. \bibitem{Hoc96} D.~Hochbaum. \newblock Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems. \newblock {\em Chapter 3 in Approximation Algorithms for NP-Hard Problems, PWS Publication Company}, 1997. \bibitem{NemTro75} G.~Nemhauser and J.~L.E.~Trotter. \newblock Vertex packings: structural properties and algorithms. \newblock {\em Mathematical Programming}, 8:232--248, 1975. \bibitem{Pas97} V.~T. Paschos. \newblock A survey of approximately optimal solutions to some covering and packing problems. \newblock {\em ACM Computing Surveys}, 29(2):171--209, June 1997. \bibitem{Pit84} L.~Pitt. \newblock Simple probabilistic approximation algorithm for the vertex cover problem. \newblock {\em Technical Report, Yale}, June 1984. \bibitem{WilGoe95} D.~Williamson, M.~Goemans, M.~Mihail, and V.~Vazirani. \newblock A primal-dual approximation algorithm for generalized steiner network problems. \newblock {\em Combinatorica}, 15:435--454, 1995. %--------------------------------------------------------- \end{thebibliography} \end{document}