% Hadas 4343, 8532334
% Yvonne 8341012 
% 1997

\newenvironment{Pf}{\par\noindent{\bf Proof.}}{\mbox{}\hfill$\Box$}
%\omega 
%\omega_1, \omega_2
%\delta, \Delta, \Deltav, \Deltae
\documentstyle[12pt,doublespace]{article}
%\def\QED{\quad\blackslug\lower 8.5pt \null\par}
\renewcommand{\baselinestretch}{1.1}
\topmargin= -20pt
\oddsidemargin= -12pt
\evensidemargin= -12pt
\textwidth=6.5in
\textheight=9in
\newtheorem{theorem}{Theorem}
\newtheorem{proof}{Proof}       
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\renewcommand{\thetheorem}{\thesection.\arabic{theorem}}
\renewcommand{\theproof}{\thesection.\arabic{proof}}
 \setcounter{theorem}{0}\setcounter{lemma}{0}
\begin{document}
\bibliographystyle{abbrv}      %%%%%%%%%%%%%%%%%%%%%%%
\input{epic.sty} \input{eepic.sty}
%from shaulm
%\newcommand{\NN}{\mbox{$N \times N$}}
%\newcommand{\ALG}{\mbox{Micro-Hillary}}
%\newcommand{\PARALG}{Parametric Micro-Hillary}
%
%\newcommand{\PROOF}{\noindent {\bf Proof:}\\ \indent } 
%\newcommand{\ENDPROOF}{\mbox{$\Box$}}
%
%\newcommand{\SS}{\scriptscriptstyle}
%\newcommand{\arrstr}{0.5}
%\newcommand{\eqnstr}{0.7}
%\newcommand{\STD}{\scriptsize}
%end from shaulm
\newcommand{\ToR}      {\rightarrow \Re^+}
\newcommand{\W}     {\omega}
\newcommand{\B}     {\Delta_E}
\newcommand{\WH}     {\varpi}
\newcommand{\WToR}  {\W: V \ToR}
\newcommand{\Len}   {\ell}
\newcommand{\LToR}{\Len: E \ToR}
\newcommand{\Demand}   {\widehat{\ell}}
\newcommand{\Deg}   {\widehat{d}}
\newcommand{\DemandInR}{\Demand \in \Re^+}

\title{Approximation Algorithm\\
for the Partial Set-Covering Problem
%(or for the Generalized Knapsack Problem)
\footnote{ 
This research was supported by the U.D. Erteschik fund
 for practical research.}}
 \author{Reuven Bar-Yehuda\\
 Computer Science Department\\
 Technion - IIT, Haifa  32000 Israel\\
\\
 e-mail: reuven@cs.technion.ac.il\\
 http://www.cs.technion.ac.il/$\sim$reuven}
 %http://www.cs.technion.ac.il/\~\ reuven}
\begin{spacing}{1}
 \maketitle

\begin{abstract}
In this paper, we consider the following
natural generalization of two fundamental problems:
the Set-Cover and the Min-Knapsack problem.
We are given a hypergraph $H = (V,E)$. Each vertex $v \in V$
has a weight $\W (v) \geq 0$ and each edge $e \in E$ a
length $\Len (e) \geq 0$. Given also $\Demand>0$, our
objective is to find $C \subseteq V$ with minimum total
weight $\W(C)$, such that $\Len(E(C)) \geq \Demand$ (where:
$\Len(\cdot)$ denotes the total length and
$E(C)$ denotes the set of edges adjacent to vertices
in $C$).
We present an
$O(|V|^2 +|E|\B)$-time, $O(|V|+|E|)$ space,
$\B$-approximation algorithm for this problem, where
$\B \geq 2$ is an upper bound on the edge cardinality of the hypergraph.
The special case in which all the edges have unit length
called the $\Demand$-Set-Cover problem, has been studied by Kearns
\cite{Ke90} and later
by Slav\'{\i}k \cite{Sla97} and later by Burroughs \cite{Bu98}.
The special case in which all the edges have unit length
and the edge cardinality is exactly 2, called the
$\Demand$-Vertex-Cover problem, was studied by
Bshouty and Burroughs \cite{BB98}. They presented a
2-approximation algorithm 
but the time was much higher than 
our $O(|V|^2)$ time.

The special degenerate case where all hyper-edge
cardinality is $1$ is the
variation of the Knapsack algorithm, there, our
generalized algorithm becomes the well known greedy
algorithm.

Our approximation algorithm was developed by
using the local-ratio technique. The main idea is to
subtract repeatedly a homogeneous weight function from
the given weight function.

\end{abstract}

\noindent{\bf Keywords:}
Approximation Algorithm, Local Ratio, Covering
Problems, Vertex Cover, Set Cover, Partial Covering,
Knapsack.

\end{spacing}

\renewcommand{\baselinestretch}{1.1}
\newpage



\section{Introduction}
 \setcounter{theorem}{0}\setcounter{lemma}{0}
 \setcounter{equation}{0}

We are given a hypergraph $H$ = $(V,E)$, a weight function $\WToR$,
a length function $\LToR$, and a covering
requirement $\DemandInR$. Define:

$\W   (V')= \sum_{v \in V'} \W (v)$ for $V' \subseteq V$.

$\Len (E')= \sum_{e \in E'} \W (e)$ for $E' \subseteq E$.

$E(V')= \{e \in E: e \cap V' \neq \phi \}.$

$E(v)=E(\{v\}).$

$d(v)=|E(v)|.$

$\Delta_V=\max_{v\in V} d(v).$

$\B=\max \{2,$ $\max_{e\in E} |e|\}.$

We say that $C$ is a {\em feasible solution} (or just
an $\Demand${\em -cover}) if $C \subseteq V$
and $\Len(E(C)) \geq \Demand$. An $\Demand$-cover $C^*$ is optimal
if $\W(C^*) \leq \W(C)$ for all feasible solutions $C$.
A feasible solution $C$ is called an {\em $r$-approximate cover}, if
$\W(C) \leq r \cdot \W(C^*)$.

An algorithm $A$ is called an $r$-approximation algorithm if for all
instances $H,\W,\Len,\Demand$, $A$ returns an $r$-approximate cover.

Notice that there is a feasible solution iff
$\Len(E)\geq \Demand$. In the special case where $\Len(E)=\Demand$ 
the length function $\Len$ is redundant and we get
the well known classic problem, the Set Cover problem.

\subsection{Some History of The Vertex and the Set Cover Problems}
A set $C \subseteq V$ is called a {\em vertex cover}
of a graph $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 graph $G = (V,E)$ and a weight
function $\WToR$, find a vertex cover $C$ with minimum total weight.
The vertex
cover problem (VC) is NP-hard even for planar cubic
graphs with unit weights \cite{GarJoh79}.
For unit weight vertex cover, Gavril (see
\cite{GarJoh79}) suggested a linear time
2-approximation algorithm. For the general vertex
cover problem, Nemhauser and Trotter \cite{NemTro75}
developed a local optima algorithm that implies a
2-approximation.
%, see \cite{Hoc80}, \cite{Hoc83}, \cite{Hoc96}.

Currently
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}. Recently, Bar-Yehuda
\cite{Bar98} has presented
a unified approach and a generic approximation
algorithm for a family for covering problems.
The algorithm is this paper is
generated by this approach.

The {\em set-cover} problem is a generalization of
the vertex cover problem.
A set $C \subseteq V$ is called a {\em set cover}
of a hypergraph $H=(V,E)$ if every 
(hyper)edge has at least one endpoint in $C$,
i.e., $\forall_{e \in E}\ e \cap C \neq \phi$. The set cover
problem (SC) is: given a hypergraph $H = (V,E)$ and a weight
function $\WToR$ find a set cover $C$ with minimum total weight.
The best known approximation algorithms for SC are:
Chv\'{a}tal's \cite{Chv79} $(\ln \Delta_V)$-approximation and
Bar-Yehuda and Even's \cite{BarEve81} linear time
$\B$-approximation algorithm.
% where $\Delta_V$ is the
%maximum vertex degree and $\B$ is the maximum edge
%degree (cardinality).

\subsection{History of The Unit-Length Partial Covering Problems}
%$\Demand$-Vertex Cover Problem}

The first time the partial cover problem was mentioned
in the literature was by Kearns\cite{Ke90} in relation to learning.
In this excellent PhD dissertation, the
Chv\'{a}tal greedy approach is studied. Later Slav\'{\i}k \cite{Sla97}
showed that the $(\ln \Delta_V)$-approximation of set
cover is extended to the case in which $\Demand=p \cdot |E|$
for a given constant $0<p<1$. Only recently, 
Burroughs in her master thesis \cite{Bu98} extended this
result to general $\Demand \leq |E|$. For the special case of
$\B=2$, the $\Demand$-vertex cover problem,
Bshouty and Burroughs \cite{BB98} presented a 2-approximation,
polynomial-time algorithm which is based on solving a linear
program. They also showed that improving the ratio to a constant
smaller than 2, would be a breakthrough. They have showed that
such an improvement on many families of instances
would imply improving the ratio for the classic VC
as well.

\subsection{Overview}

In section 2 we define the homogeneous weight
function and prove its useful properties. In section
3 we present the $\B$-approximation algorithm. The
main step of this algorithm is a subtraction of
homogeneous weight function. Using the properties of
the homogeneous function and the local ratio
technique we prove it correctness.

\section{The Homogeneous Weight Function}
 \setcounter{theorem}{0}\setcounter{lemma}{0}
 \setcounter{equation}{0}
Given $H,\Len,\Demand$, we denote by $E(v)$ the set of
edges adjacent to $v$. The effective degree of $v$ is:
$\Deg(v)=\min\{\Demand, \Len(E(v))\}$.

With respect to $H,\Len,\Demand$, a weight function $\WH$ is called
homogeneous if $\WH = \Deg$. The main valuable property
of the homogeneous weight function is that any minimal cover
is a "good" approximation. An $\Demand$-cover $C$ is minimal if
$\forall_{v \in V} C\backslash\{v\}$ is not an $\Demand$-Cover.
In the next two lemmas we show
this by proving that the total weight of any
minimal $\Demand$-Cover is in the interval: $[\Demand,\B\Demand]$.

\begin{lemma} \label{le:b1}
Let $\WH$ be an homogeneous weight function with
respect to
$H,\Len,\Demand$. If C is any $\Demand$-cover, then
$\WH(C)\geq \Demand$
\end{lemma}

\begin{Pf}
%\vspace*{0.2cm}

\begin{tabular}{lll}
$\WH(C)$ &$=\sum_{v\in C} \WH(v)$ & [by definition]\\
         &$=\sum_{v\in C}\Deg(v)$ & [$\WH$ is homogeneous]\\
         &$= \sum_{v\in C}\Len(E(v))$ &
[otherwise it is $\Demand$ and we are done]\\
         &$\geq \Len(E(C))$ & [$E(C)=\bigcup_{v \in C} E(v)$]\\
         &$\geq \Demand$ & [by definition of $\Demand$-cover]
\end{tabular}
\vspace{0.2cm}

\end{Pf}

%\hfill $\Box$		\\

\begin{lemma} \label{le:b2}
Let $\WH$ be an homogeneous weight function
with respect to
$H,\Len,\Demand$. If C is any minimal $\Demand$-cover, then
$\WH(C)\leq \B \cdot \Demand$, where $\B\geq 2$ is an upper
bound on the hyper-edge cardinality.
\end{lemma}

\begin{Pf}
We can assume that $|C| \geq \B$ since 
otherwise the claim is proven by:
$\WH(C) = \sum_{v \in C}\WH(v) \leq |C|\cdot
\max_{v\in C}\WH(v) \leq |C| \cdot \Demand \leq \B \cdot \Demand$.
We can also assume $\forall_{v\in C}\Deg(v)=\Len(E(v))<\Demand$.
We partition $E(C)$ into two sets: the set of edges "covered"
by exactly one endpoint in $C$: $E_1=\{e:|e \cap C|=1\}$,
and the others that are "covered" by more endpoints:
$E_2=\{e:|e\cap C| >1\}$.

Now,
%\vspace*{0.2cm}

\begin{tabular}{lll}
$\WH(C)$ &$=\sum_{v\in C} \WH(v)$ & [by definition]\\
         &$=\sum_{v\in C}\Deg(v)$ & [$\WH$ is homogeneous]\\
         &$=\sum_{v\in C}\Len(E(v))$ & [by our assumption]\\
         &$\leq \B \cdot \Len(E_2)+\Len(E_1)$ &
           [by definition of $E_1, E_2$]\\
         &$=\B \cdot \Len(E)-(\B-1)\cdot\Len(E_1)$ &
           [by definition of $E_1, E_2$]\\
         &$=\B \cdot (\Demand+\Demand')-(\B-1)\cdot\Len(E_1)$ &
[Define: $\Demand'=\Demand-\Len(E(C))$]\\
         &$\leq \B \cdot (\Demand+\Demand')-\Len(E_1)$ &
           [$\B \geq 2$]\\
         &$=\B \cdot \Demand+(\B \cdot \Demand'-\Len(E_1))$ & [and...]\\
         &$?\leq \B \cdot \Demand+0$ &
           [for this we need to show: $\Len(E_1) \geq \B \cdot \Demand'$].
\end{tabular}
\vspace{0.2cm}

So, now we only need to show that $\Len(E_1) \geq \B\cdot \Demand'$.
Let $v \in C$, define $E_1(v) = E_1 \cap E(v)$. Since
$C$ is a minimal $\Demand$-cover,
$\Len(E(C\backslash\{v\})) < \Demand$. The "contribution" of $v$
to the total length must therefore satisfy: $\Len(E_1(v))>\Demand'$. This is true
for all vertices in C, and therefore $\Len(E_1)>|C| \cdot \Demand'$.
Since we assumed $|C| \geq \B$, we get
$\Len(E_1)>\B \cdot \Demand'$.


\end{Pf}

Now, let us extend the definition of the homogeneous weight
function. $\WH$ is homogeneous with respect to
$H,\Len,\Demand$ if
$\exists_{\epsilon>0}\forall_{v\in V} \WH(v)=\epsilon \cdot \Deg(v)$.
We conclude this section with the
following useful theorem:
\begin{theorem} \label{th:b1}
Let $\WH$ be an homogeneous weight function
with respect to
$H,\Len,\Demand$. If $C$ is a minimal $\Demand$-cover and $C^*$ is
an optimal one, then $\WH(C) \leq \B\WH(C^*)$.
\end{theorem}

\begin{Pf}
\vspace*{0.2cm}

\begin{tabular}{lll}
$\WH(C)$ & $\leq \cdot \B\cdot \epsilon\cdot \Demand$ & [by lemma \ref{le:b2}]\\
         &$\leq \B\cdot \WH(C^*)$ & [by lemma \ref{le:b1}]
\end{tabular}
\vspace{0.2cm}

\end{Pf}
%\hfill $\Box$		\\

%\newpage
\section{The $\B$-approximation algorithm}
\setcounter{theorem}{0}
\setcounter{equation}{0}

For methodical purposes, the algorithm is written in a recursive fashion.
To get to the main algorithmic step, we first have to take care of the
trivial cases. After we deal with these trivial cases we
will be able to assume: $|E|>0,\ \forall_{v\in V} \W >0$
and $\Demand>0$. Under these assumptions we will be able to
subtract from $\W$ a homogeneous function $\W_1$.
The algorithm is described in Figure
\ref{fig:cover-algorithm}.


\newcommand{\Cover}{{\bf Cover}}

\newcommand{\TABLINE}[1]{\hspace*{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\=\hspace{#1}\= 
\kill}

\begin{figure}[htb]
\begin{center}
\fbox{
\begin{minipage}{8cm}
\begin{tabbing}
\TABLINE{0.5cm}
{\bf Algorithm  Cover $(V,E, \omega, \Len, \Demand)$}\\
%**(LB??) Do you also want to have \Len as one of the inputs?
%** I thought it should be "global" since
%**it is a constarnt for all recursion calls
\> If $\Demand\leq 0$\\
\> \> return $\phi$\\
\> If $E=\phi$\\
\> \> return "no solution"\\
\> $V_0 = \{v:\Deg(v)=0\}$\\
\> If $V_0 \neq \phi$\\
\> \> return  \Cover ($V \backslash V_0$, $E\backslash E(V_0)$,
$\W, \Len, \Demand)$\\
\> $V_0 = \{v:\W (v)=0\}$\\
\> If $V_0 \neq \phi$\\
\> \> return $V_0\cup$ \Cover ($V \backslash V_0$,
$E\backslash E(V_0)$, 
$\W, \Len, \Demand-|\Len(E(V_0))|)$\\
\\
\> /*{\bf At this point, $\Demand>0,\ E \neq \phi,$
$\W(\cdot)>0,\ \Deg\cdot)>0$}*/\\
\> /*{\bf so we can find a homogeneous weight function to subtract}*/\\
\> $\epsilon=\min_{v\in V} \frac{\W(v)}{\Deg(v)}$\\
\> for each $v \in C$\\
\> \>$\W_1(v)=\epsilon \cdot \Deg(v)$\\
\> \>$\W_2(v) = \W (v)-\W_1(v)$\\
\\
\> /*{\bf Main recursion call, and the removal loop}*/\\
\> $C$= \Cover $(V,E, \W_2, \Len, \Demand)$\\
\> for each $v \in C$\\
\> \> if $C\backslash \{v\}$ is a $\Demand$-cover \\
\> \> \>$C=C\backslash\{v\}$\\
\> return $C$

\end{tabbing}
\end{minipage}
}
\end{center}
\caption{\label{fig:cover-algorithm}
\small
Algorithm {\bf Cover}}
\end{figure}
\begin{lemma} \label{le:b3}
Algorithm \Cover\ gives a $\B$-approximation.
\end{lemma}

\begin{Pf}
We prove this by induction on $|E|+|V|$.
\\
{\bf Base:} Trivial.
\\
{\bf Step:} We can assume $\Demand>0,\ E \neq \phi,\ \W(\cdot)>0,\ \Deg(\cdot)>0$,
since, if not, the induction step is trivial. So, we
now consider the cover $C$ produced by the main
recursive call and after the removal loop has made sure
it is a minimal $\Demand$-cover. Let $C^*$, $C_1^*$, and $C_2^*$
be optimal $\Demand$-covers with respect to $\W$, $\W_1$, and $\W_2$.
Now,

\vspace*{0.2cm}
\begin{tabular}{lll}
$\W(C)$ & $= \W_1(C)+\W_2(C)$ & [by the algorithm definition]\\
        &$\leq \B\W_1(C_1^*)+\B\W_2(C_2^*)$
         & [by theorem \ref{th:b1} and induction hyp.]\\
        &$\leq \B\W(C^*)$ & [$\W_1$, $\W_2$ are relaxations of $\W$]
\end{tabular}

\end{Pf}

\begin{lemma} \label{le:b4}
Algorithm \Cover\ can be implemented in $O(|V|^2+|E|\B)$
time and $O(|V|+|E|)$ space.
\end{lemma}

\begin{Pf}
To maintain the value of $\Deg$, we only need to
hold
and maintain the value of $\Len(E(v))$ at each non-deleted
node $v \in V$. This value may change only
when one of its neighbors is deleted. When a node is
deleted it updates all of its neighbors. 
Summing this up
over the edges, the time taken is

$\sum_{e \in E}|e|^2 \leq \B\sum_{e \in E}|e| = \B|E|$

We need to show that all other operations take $O(|V|^2)$
time.
The total number of iterations is bounded by $2|V|$.
This is because at each iteration either a node is
deleted (belongs to $V_0$), or a weight of a node becomes $0$.
At each iteration we need $O(|V|)$ other operations.

\end{Pf}

\begin{theorem} \label{th:b2}
For simple graphs the $\Demand$-Vertex Cover problem has
an $O(|V|^2)$ time 2-approximation algorithm.
\end{theorem}

\begin{Pf}
Since $|E|\leq|V|^2$ and from lemmas \ref{le:b3}, \ref{le:b4}.

\end{Pf}

\noindent{\bf Acknowledgment}\\
We would like to thank Lynn Burroughs for her
careful reading and suggestions,
and Hadas Harier for typing.

\renewcommand{\baselinestretch}{1.0}
\bibliography{paper}
\end{document}