% KMK, epub/pagination, 12/6/05
% DXR FINAL CORREX 11/17/05
% SAB First Pass 8/29/05
% SAB Pretext 4/25/05
\documentclass[final,leqno]{siamltex704}
%\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{epsfig}
\usepackage{ifthen}
%\usepackage{fullpage}
%\usepackage{pstricks}
%\usepackage{pst-node}
%\sloppy
\renewcommand{\ldots}{\ensuremath{\dotsc}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\comment}[1]{}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\ceil}[1]{\left\lceil {#1} \right\rceil}
\newcommand{\floor}[1]{\left\lfloor {#1} \right\rfloor}
\newcommand{\paren}[1]{\left( #1 \right)}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\bitset}{ \set{0,1} }
\newcommand{\bit}{\set{0,1}}
\newcommand{\nbits}{\bit^n}
\newcommand{\kbits}{\bit^k}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\inv}[1]{\frac{1}{#1}}
\newcommand{\code}[1]{\left\langle #1 \right\rangle}
\newcommand{\eqdef}{\stackrel{\scriptscriptstyle \triangle}{=}}
\def\maps11{\stackrel {1-1}{\longmapsto}}
\newcommand{\pr}{{\mbox{Pr}}}
\newcommand{\nil}{\mbox{\textsc{nil}}}
\newcommand{\true}{\mbox{\textsc{true}} }
\newcommand{\false}{\mbox{\textsc{false}} }
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\ds}{\displaystyle}
%\newcommand{\qed}{$\blacksquare$}
%\newtheorem{theorem}{Theorem}
%\newtheorem{definition}{Definition}
%\newtheorem{remark}{Remark}
%\newtheorem{lemma}{Lemma}
%\newtheorem{proposition}{Proposition}
%\newtheorem{claim}{Claim}
%\newtheorem{conjecture}{Conjecture}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{observation}{Observation}
%\newcounter{spuriouscounter}
%\renewcommand{\thespuriouscounter}{} % don't want numbering
%\newtheorem{spuriousprop}[spuriouscounter]{Spurious Proposition}
%\newtheorem{lemma*}[spuriouscounter]{Lemma}
%\newtheorem{corollary*}[spuriouscounter]{Corollary}
%\newenvironment{proof}{\noindent {\bfseries Proof.} }{\hfill\qed\vspace{1em}}
\newenvironment{spuriousproof}{ {\bfseries Spurious Proof.} }%
{\hfill\qed\vspace{1em}}
\newenvironment{proofsketch}{ {\bfseries Proof Sketch.} }%
{\hfill\qed\vspace{1em}}
\newenvironment{aproof}[2]{ {\bfseries Proof of {#1} \ref{#2}.} }%
{\hfill\qed\vspace{1em}}
\newsavebox{\saveboxtxt}
\newenvironment{boxit}{\begin{lrbox}{\saveboxtxt}%
\begin{minipage}[b]{0.9\textwidth}}{\end{minipage}\end{lrbox}%
\fbox{\usebox{\saveboxtxt}}}
\newenvironment{myboxit}{\begin{lrbox}{\saveboxtxt}%
\begin{minipage}[b]{\textwidth}}{\end{minipage}\end{lrbox}%
\fbox{\usebox{\saveboxtxt}}}
\newsavebox{\progbox}
\newsavebox{\progtitlebox}
\newlength{\titleskip}
\newlength{\codeindent}
\newlength{\linenumwidth}
\newlength{\linenumindent}
\newlength{\pauseskip}
\newlength{\indentskip}
\newlength{\defaultlinenumwidth}
\newcounter{lynecount}
\newcounter{startflag}
\newcommand{\defaultlinenumtext}{10.}
\newenvironment{program}[2][\defaultlinenumtext]
{\addvspace{1em}\begin{lrbox}{\progtitlebox}{\bfseries #2}\end{lrbox}
\setcounter{lynecount}{0}
\setcounter{startflag}{0}
\setlength{\pauseskip}{8pt}
\setlength{\indentskip}{1cm}
\setlength{\linenumindent}{4mm}
\setlength{\titleskip}{1em}
\settowidth{\linenumwidth}{#1}
\addtolength{\linenumindent}{\linenumwidth}
\setlength{\codeindent}{6mm}
}
{\ifthenelse{\value{startflag} = 0}{\startprog}{}
\end{tabbing}\end{minipage}\end{lrbox}
\begin{center}\fbox{\usebox{\progbox}}\end{center}
\vspace{1em}
}
\newcommand{\startprog}
{\setcounter{startflag}{1}
\begin{lrbox}{\progbox}
\begin{minipage}[b]{\textwidth}\begin{tabbing}
\hspace{\linenumindent}\=%
\hspace{\codeindent}\=\hspace{\indentskip}\=%
\hspace{\indentskip}\=\hspace{\indentskip}\=%
\hspace{\indentskip}\=\hspace{\indentskip}\=\kill
\usebox{\progtitlebox}\rule[-\titleskip]{0pt}{0pt}\\
}
\newcommand{\lyne}[1][\}]
{\ifthenelse{\value{startflag} = 0}{\startprog}{\rule{1.5\codeindent}{0pt}\\}
\refstepcounter{lynecount}
\ifthenelse{\equal{#1}{\}}}{}{\label{#1}}
\>\llap{\thelynecount.}\>
}
\newcommand{\cont}{\ifthenelse{\value{startflag} = 0}{\startprog}
{\rule{\codeindent}{0pt}\\}\>\>}
\newcommand{\pause}[1][1]{\rule[-#1\pauseskip]{0pt}{0pt}}
\newenvironment{algorithm}[2][\defaultlinenumtext]
{\begin{program}[#1]{Algorithm #2}}{\end{program}}
\newenvironment{subroutine}[2][\defaultlinenumtext]
{\begin{program}[#1]{Subroutine #2}}{\end{program}}
\newenvironment{indentpar}[2]{\begin{lrbox}{\saveboxtxt}%
\setlength{\wdth}{#1\textwidth}\settowidth{\iwdth}{#2}%
\addtolength{\wdth}{-\iwdth}\begin{minipage}[t]{\wdth}}%
{\end{minipage}\end{lrbox}\usebox{\saveboxtxt}}
\newenvironment{proglines}[1][\defaultlinenumtext]
{\setcounter{lynecount}{0}
\setcounter{startflag}{0}
\setlength{\pauseskip}{8pt}
\setlength{\indentskip}{1cm}
\setlength{\linenumindent}{4mm}
\setlength{\titleskip}{1em}
\settowidth{\linenumwidth}{#1}
\addtolength{\linenumindent}{\linenumwidth}
\setlength{\codeindent}{6mm}
\let\lyne\alglyne
}
{\ifthenelse{\value{startflag} = 0}{\startproglines}{}
\end{tabbing}\end{minipage}\end{lrbox}
\begin{center}\mbox{\usebox{\progbox}}\end{center}
}
\newenvironment{alglines}[1][\defaultlinenumtext]
{\begin{proglines}[#1]}{\end{proglines}}
\newcommand{\startproglines}
{\setcounter{startflag}{1}
\begin{lrbox}{\progbox}
\begin{minipage}[b]{\textwidth}\begin{tabbing}
\hspace{\codeindent}\=\hspace{\indentskip}\=%
\hspace{\indentskip}\=\hspace{\indentskip}\=%
\hspace{\indentskip}\=\hspace{\indentskip}\=\kill
}
\newcommand{\alglyne}[1][\}]
{\ifthenelse{\value{startflag} = 0}{\startproglines}{\rule{1.5\codeindent}{0pt}\\}
\refstepcounter{lynecount}
\ifthenelse{\equal{#1}{\}}}{}{\label{#1}}
\>
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\NP}{\mbox{NP}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\Py}{\mathcal{P}}
\newcommand{\Q}{\mathcal{Q}}
\newcommand{\T}{\mathcal{T}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\N}{N^{-}}
\newcommand{\tI}{J}
\newcommand{\opt}{\mbox{\textsc{Opt}}}
\newcommand{\sol}{\mbox{\textsc{Sol}}}
\renewcommand{\subset}{\varsubsetneq}
\newcommand{\splits}{\mbox{\textsc{Split}}}
\newcommand{\splitsf}{\mbox{\textsc{\footnotesize Split}}}
%\newcommand{\anote}[1]{\begin{quote}{\bf Author's personal note:} #1\end{quote}}
%\newcommand{\anote}[1]{\textbf{Author's note}: #1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{On the Equivalence between the Primal-Dual Schema and
the Local Ratio Technique\thanks{Received by the editors February 26, 2005; accepted for publication (in revised form)
March 28, 2005; published electronically December 7, 2005. An extended abstract containing some of these results was presented at the 4th
International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'01)~\cite{BarRaw01b}.
\URL sidma/19-3/62538.html}}
\author{Reuven Bar-Yehuda\thanks{Department of Computer Science, Technion, Haifa 32000, Israel (reuven@cs.technion.ac.il).
The research of this author was supported by the N. Haar and R. Zinn Research Fund.}
\and Dror Rawitz\thanks{School of Electrical Engineering, Tel-Aviv University, Tel-Aviv 69978, Israel (rawitz@eng.tau. ac.il).
This research was done while the author was a Ph.D. student at the Computer Science Department
of the Technion.}}
\begin{document}
\slugger{sidma}{2005}{19}{3}{762--797}
\setcounter{page}{762}
\maketitle
\begin{abstract}
We discuss two approximation paradigms that were used to construct
many approximation algorithms during the last two decades, the
{\em primal-dual schema} and the {\em local ratio technique}.
Recently, primal-dual algorithms were devised by first constructing
a local ratio algorithm and then transforming it into a primal-dual
algorithm. This was done in the case of the $2$-approximation
algorithms for the {\em feedback vertex set} problem and in the
case of the first primal-dual algorithms for maximization problems.
Subsequently, the nature of the connection between the two paradigms
was posed as an open question by Williamson [{\it Math.~Program.}, 91 (2002), pp.~447--478]. In this
paper we answer this question by showing that the two paradigms are
equivalent.
%
%The equivalence
%between the paradigms is constructive, and it implies that the
%integrality gap of an integer program serves as a bound to the
%approximation ratio when working with the local ratio technique.
\end{abstract}
%\noindent
%\textbf{Keywords}:
\begin{keywords}
approximation algorithms, combinatorial optimization,
covering problems, local ratio, primal-dual
\end{keywords}
%\noindent
%\textbf{Subject Classification}:
%Analysis of algorithms: Suboptimal algorithms.
%Programming: Integer, Algorithms, Heuristic.
\begin{AMS}
68W25, 90C27
\end{AMS}
\begin{DOI}
10.1137/050625382
\end{DOI}
\pagestyle{myheadings}
\thispagestyle{plain}
\markboth{REUVEN BAR-YEHUDA AND DROR RAWITZ}{PRIMAL-DUAL SCHEMA AND
THE LOCAL RATIO TECHNIQUE}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%\cite{Hoc97}
\subsection{Primal-dual schema}
A key step in designing an approximation algorithm is establishing a
good bound on the value of the optimum. This is where linear
programming helps out. Many combinatorial optimization problems can
be expressed as linear integer programs, and the value of an optimal
solution to their {\em LP-relaxation} provides the desired bound.
Clearly, the best we can hope for using this approach is to get an
$r$-approximation algorithm, where $r$ is the {\em integrality gap} of
the program. One way to obtain approximate solutions is to solve the
LP-relaxation and then to {\em round} the solution while ensuring that
the cost does not change by much. Another way to go about it is to
use the {\em dual} of the LP-relaxation in the design of approximation
algorithms and their analyses. A {\em primal-dual} $r$-approximation
algorithm constructs a feasible integral primal solution and a
feasible dual solution such that the value of the primal solution is
no more than $r$ times (or, in the maximization case, at least $1/r$
times) the value of the dual solution. This work focuses on classical
primal-dual approximation algorithms, specifically those that fall
within the so-called {\em primal-dual schema}.
The primal-dual schema can be seen as a modified version of the
{\em primal-dual method for solving linear programs}. The
primal-dual method was originally proposed by Dantzig, Ford, and
Fulkerson~\cite{DFF56}. Over the years, it became an important tool
for solving combinatorial optimization problems that can be formulated
as linear programs. While the {\em complementary slackness
conditions} are imposed in the primal-dual method, we enforce the
primal conditions and relax the dual conditions when working with the
primal-dual schema. A primal-dual approximation algorithm typically
constructs an approximate primal solution and a feasible dual solution
simultaneously. The approximation ratio is derived from comparing the
values of both solutions. The first approximation algorithm to use
the primal-dual schema is Bar-Yehuda and Even's approximation
algorithm for the {\em weighted set cover} problem~\cite{BarEve81},
and since then many approximations algorithms for \NP-hard
optimization problems were constructed using this approach, among
which are algorithms for {\em network design} problems (see,
e.g.,~\cite{RK93,AKR95,GoeWil95b}). In fact, this line of research
has introduced the idea of looking at {\em minimal} solutions (with
respect to set inclusion) to the primal-dual schema.
Several primal-dual approximation frameworks were proposed in the last
decade. Goemans and Williamson~\cite{GoeWil95b} presented a generic
algorithm for a wide family of {\em network design} problems. They
based a subsequent survey of the primal-dual schema~\cite{GoeWil97} on
this algorithm. Another, more recent, survey by
Williamson~\cite{Wil02} describes the primal-dual schema and several
extensions of the primal-dual approach. In~\cite{GoeWil97} the
authors show that the primal-dual schema can be used to explain many
classical (exact and approximation) algorithms for special cases of
the {\em hitting set} problem, such as {\em shortest path}, {\em
minimum spanning tree}, and {\em vertex cover}.
%An advancement step in these algorithms can be informally described as
%follows: find a collection of sets that satisfies a certain property,
%and, then, increase the dual variables corresponding to these sets as
%much as possible without losing feasibility.
Following~\cite{GoeWil95b}, Bertsimas and Teo~\cite{BerTeo98} proposed
a primal-dual framework to design and analyze approximation algorithms
for integer programming problems of the covering type. As
in~\cite{GoeWil95b,GoeWil97} this framework enforces the primal
complementary slackness conditions while relaxing the dual conditions.
However, in contrast to previous studies, Bertsimas and
Teo~\cite{BerTeo98} express each advancement step as the construction
of a single valid inequality and an increase of the corresponding
dual variable (as opposed to an increase of several dual variables).
The approximation ratio of the resulting algorithm depends upon the
quality, or {\em strength} in terms of~\cite{BerTeo98}, of the
inequalities that are used.
%%%%%
\subsection{Local ratio technique}
The local ratio technique uses weight subtractions. An advancement
step of a local ratio algorithm typically consists of the construction
of a new {\em weight function}, which is then subtracted from the
current objective function. Each subtraction changes the optimum, but
incurs a cost. The ratio between this cost and the change in the
optimum is called the {\em effectiveness} of the weight function. The
approximation ratio of a local ratio algorithm depends on the
effectiveness of the weight functions it constructs.
The local ratio approach was developed by Bar-Yehuda and
Even~\cite{BarEve85} in order to approximate the {\em set cover} and
{\em vertex cover} problems. In that paper the authors presented a
local ratio analysis to their primal-dual approximation algorithm for
{\em set cover}~\cite{BarEve81} and a $(2-\frac{\log \log n}{2\log
n})$-approximation algorithm for vertex cover. About ten years
later Bafna, Berman, and Fujito \cite{BBF99} extended the {\em local ratio lemma}
from~\cite{BarEve85} in order to construct a $2$-approximation
algorithm for the {\em feedback vertex set} problem. This algorithm
was the first local ratio algorithm that used the notion of {\em
minimal} solutions. We note that this work and the
$2$-approximation from~\cite{BecGei96} were essential in the design of
primal-dual approximation algorithms for {\em feedback vertex
set}~\cite{CGHW98}. Following Bafna, Berman, and Fujito \cite{BBF99},
Fujito~\cite{Fuj98} presented a generic local ratio algorithm for node
deletion problems with nontrivial and hereditary graph properties.%
\footnote{A graph property $\pi$ is {\em nontrivial} if it is true for
infinitely many graphs and false for infinitely many graphs; it is
{\em hereditary} if every subgraph of a graph satisfying $\pi$
also satisfies $\pi$.}
%
Later, Bar-Yehuda~\cite{Bar00} presented a unified local ratio
approach for developing and analyzing approximation algorithms for
covering problems. This framework, which extends the one
in~\cite{Fuj98}, can be used to explain most known optimization and
approximation algorithms for covering problems. Bar-Noy et
al.~\cite{BBFNS01} use the local ratio technique to develop a
framework for resource allocation and scheduling problems. This study
was the first to present a local ratio (or primal-dual) approximation
algorithm for a natural maximization problem. A primal-dual
interpretation was presented in~\cite{BBFNS01} as well. Recently,
Bar-Yehuda and Rawitz~\cite{BarRaw04} presented local ratio
interpretations of known algorithms for {\em minimum $s$-$t$ cut} and
the {\em assignment} problem. These algorithms are the first
applications of local ratio to use negative weights. The
corresponding primal-dual analyses are based on new integer programming formulations of
these fundamental problems. A detailed survey on the local ratio
technique that includes recent developments (such as fractional local
ratio~\cite{BHNSS02}) is given in~\cite{BBFR04}.
%%%%%
\subsection{Our results}
We present two generic approximation algorithms for covering problems.
The first is a recursive version of the primal-dual algorithm
from~\cite{BerTeo98}, and the second is a variant of the local ratio
algorithm from~\cite{Bar00}. After presenting both frameworks we
discuss the connection between them. We show that a {\em strong}
valid inequality (in terms of~\cite{BerTeo98}) and an {\em effective}
weight function (in terms of~\cite{Bar00}) are equivalent notions.
Consequently, we prove that both frameworks for covering are one and
the same. We demonstrate the combined approach on a variety of
covering problems, such as {\em network design} problems and the {\em
feedback vertex set} problem. We also present a linear time
approximation algorithm for the {\em generalized hitting set} problem
(which can be viewed as a prize-collecting version of hitting set).
This algorithm extends the approximation algorithm for hitting set
from~\cite{BarEve81} and achieves a ratio of $2$ in the special case
of {\em generalized vertex cover}. Its time complexity is
significantly better than Hochbaum's~\cite{Hoc02} O$(nm \log
\frac{n^2}{m})$ $2$-approximation algorithm for this special case.
\enlargethispage*{12pt}
Next, we extend both our frameworks to include algorithms for
minimization problems that are not covered by the generic algorithms
from~\cite{BerTeo98} and~\cite{Bar00}. We show that the equivalence
between the paradigms continues to hold. We demonstrate the use of
the extended frameworks on several algorithms: a $2.5$-approximation
algorithm for {\em feedback vertex set in tournaments}~\cite{CDZ01}; a
$2$-approximation algorithm for a noncovering problem called {\em
minimum $2$-satisfiability}~\cite{GusPit92,BarRaw01}; and a
$3$-approximation algorithm for a {\em bandwidth trading}
problem~\cite{BCFN03}.
%
We show that the equivalence continues to hold in the maximization
case. We do that by developing two equivalent frameworks for
maximization problems, one in each approach. Algorithms for {\em
interval scheduling}~\cite{BBFNS01} and {\em longest path in a}
directed acyclic graph (DAG) are used to demonstrate our maximization frameworks.
It is important to note that the equivalence between the paradigms is
constructive. That is, a primal-dual algorithm that follows our
framework can be easily transformed into a local ratio algorithm, and
vice versa. A corollary to this equivalence is that the {\em
integrality gap} of a certain integer program serves as a lower
bound to the approximation ratio of a local ratio algorithm. We also
note that the nature of the connection between the two paradigms was
mentioned as an open question by Williamson~\cite{Wil02}.
We believe that this study contributes to the understanding of both
approaches and, especially, that it may help in the design of
approximation algorithms for noncovering problems and nonstandard
algorithms for covering problems. For example, we show that the
primal-dual schema can be applied as a clean-up phase whose output is
an instance of a certain type that we know how to solve by other
means. This approach is quite natural in the local ratio setting and
has been used in the $(2-\frac{\log \log n}{2 \log n})$-%
approximation algorithm for vertex cover~\cite{BarEve85} and the
$2.5$-approximation algorithm for feedback vertex set in
tournaments~\cite{CDZ01}.
%Another point of interest is that while the use of a linear objective
%function and linear advancement steps are an integral part of both
%techniques, our frameworks are not limited to linear integer programs.
%%%%%
\subsection{Related work}
Jain and Vazirani~\cite{JaiVaz01} presented a $3$-approximation
algorithm for the {\em metric uncapacitated facility location} (MUFL)
problem that deviates from the standard primal-dual paradigm. Their
algorithm does not employ the usual mechanism of relaxing the dual
complementary slackness conditions, but rather it relaxes the
{\em primal} conditions. Jain et al.~\cite{JMMSV03} developed
{\em dual fitting} algorithms for MUFL. A dual fitting algorithm
produces a feasible primal solution and an {\em infeasible} dual
solution such that (1) the cost of the dual solution dominates the
cost of the primal solution, and (2) dividing the dual solution by an
appropriately chosen $r$ results in a feasible dual solution. These
two properties imply that the primal solution is $r$-approximate.
This contrasts with the standard primal-dual approach, in which a
feasible dual solution is found and used to direct the construction of
a primal solution. Freund and Rawitz~\cite{FreRaw03} presented two
combinatorial approximation frameworks that are not based on
LP-duality. Instead, they are based on weight manipulation in the
spirit of the local ratio technique. They showed that the first
framework is equivalent to {\em dual fitting} and that the second
framework is equivalent to a linear programming--based method which they defined and
called {\em primal fitting}. The second framework can be used to
analyze the algorithm of Jain and Vazirani~\cite{JaiVaz01}.
\iffalse
Bar-Yehuda et al.~\cite{BHNSS02} have designed an approximation
algorithm that uses a novel extension of local ratio called
{\em fractional local ratio}. This algorithm starts by computing an
optimal solution, $x^*$, to an LP-relaxation of the problem, denoted
by P. Then, in the weight decomposition steps, the construction of a
new weight function is based on $x^*$, and the analysis compares the
weight of the solution returned to the weight of $x^*$. Bar-Yehuda
and Rawitz~\cite{BarRaw04c} have shown that this can be explained
using primal-dual. The first step in a fractional primal-dual
$r$-approximation algorithm is to compute $x^*$. Next, the algorithm
produces an integral primal solution $x$, and a new LP, denoted by
P$'$, that has the same objective function as P, but contains
inequalities that may not be valid with respect to the original
problem. Moreover, $x^*$ is a feasible solution of P$'$. The
algorithm also computes a solution $y$ to the dual of P$'$. The
solution $x$ is $r$-approximate, since its weight is bounded below by
the value of $y$ divided by $r$. The connection between fractional
primal-dual and fractional local ratio is not unlike the connection
between the two methods in their standard forms.
\fi
%%%%%
\subsection{Overview}
The remainder of the paper is organized as follows. In
section~\ref{Sec:Pre} we define the family of problems which we
consider in this paper and state some basic facts regarding
primal-dual and local ratio. In section~\ref{Sec:Steiner} we
demonstrate the two approaches on the {\em Steiner tree} problem. The
objective of this example is to identify the differences and
similarities between the paradigms. Section~\ref{Sec:Cover} discusses
{\em covering} problems. We present a generic primal-dual algorithm
and a generic local ratio algorithm, both for covering problems, and
we show that they are equivalent. We also show how the two generic
algorithms can be applied to several covering problems. More general
minimization frameworks are given in section~\ref{Sec:Min}, and our
maximization frameworks are given in section~\ref{Sec:Max}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries}
\label{Sec:Pre}
We consider the following optimization problem: given a nonnegative
{\em weight} vector $w \in \reals_+^n$, find a solution $x \in
\naturals^n$ that minimizes (or maximizes) the inner product $w \cdot
x$ subject to some set $\F$ of feasibility constraints on $x$. This
formulation contains, among others, all linear and integer programming problems. Usually,
we require $x \in \bit^n$, and in this case we abuse notation by
treating a vector $x \in \bit^n$ as the set of its $1$ entries, i.e.,
as $\set{j : x_j=1}$. The correct interpretation should be clear from
the context.
We define the following for a minimization (maximization) problem
$(\F,w)$. A vector $x$ is called a {\em feasible solution} if $x$
satisfies the constraints in $\F$. A feasible solution $x^*$ is {\em
optimal} if every feasible solution $x$ satisfies $w \cdot x^* \leq
w \cdot x$ ($w \cdot x^* \geq w \cdot x$). We denote by $\opt$ the
value of an optimal solution, i.e., the optimum value. A feasible
solution $x$ is called an {\em $r$-approximation} or {\em
$r$-approximate} if $w \cdot x \leq r \cdot w \cdot x^*$ ($w \cdot x
\geq \frac{1}{r} \cdot w \cdot x^*$), where $x^*$ is an optimal
solution. An algorithm is called an {\em $r$-approximation algorithm}
if it returns $r$-approximate solutions. Namely, an $r$-approximation
algorithm returns a feasible solution whose weight is no more than $r$
(at least $1/r$) times the optimum weight.
%%%%%
\subsection{Primal-dual}
This section is written in terms of minimization problems. Similar
arguments can be given in the maximization case. Also, in what follows
we assume basic knowledge of linear programming. (See,
e.g.,~\cite{PapSte82,Kar91} for more details about linear
programming.)
Consider the linear program
\[
\begin{array}{lll}
\min & \ds \sum_{j=1}^n w_j x_j
& \\
\mbox{s.t.} & \ds \sum_{j=1}^n a_{ij} x_j \geq b_i
& \forall i \in \set{1,\ldots,m}, \\
& x_j \geq 0
& \forall j \in \set{1,\ldots,n}
\end{array}
\]
and its dual
\[
\begin{array}{lll}
\max & \ds \sum_{i=1}^n b_i y_i
& \\
\mbox{s.t.} & \ds \sum_{i=1}^n a_{ij} y_i \leq w_j
& \forall j \in \set{1,\ldots,n}, \\
& y_i \geq 0
& \forall i \in \set{1,\ldots,m}.
\end{array}
\]
A primal-dual $r$-approximation algorithm for a minimization problem
produces an integral primal solution $x$ and a dual solution $y$ such
that the weight of the primal solution is no more than $r$ times the
value of dual solution. Namely, it produces an integral solution $x$
and a solution $y$ such that
\begin{equation}
\label{Eqn:Bound}
w x \leq r \cdot b y.
\end{equation}
The weak duality theorem implies that $x$ is $r$-approximate.
One way to design an algorithm that finds a pair of primal and dual
solutions that satisfies (\ref{Eqn:Bound}) is to restrict our
attention to a specific kind of pairs of primal and dual solutions.
Consider a primal solution $x$ and a dual solution $y$. The duality
theorem provides us with a way to characterize a pair of optimal
solutions. Specifically, $x$ and $y$ are optimal if and only if the
following conditions, called the {\em complementary slackness
conditions}, are satisfied:
\[
\begin{array}{llll}
\mbox{Primal conditions:} & \forall j, \ x_j > 0 & \Rightarrow
& \ds \sum_{i=1}^m a_{ij}y_i = w_j. \\
\mbox{Dual conditions:} & \forall i, \ y_i > 0 & \Rightarrow
& \ds \sum_{j=1}^n a_{ij}x_j = b_i.
\end{array}
\]
However, we are interested in approximate solutions, and thus it seems
natural to relax the complementary slackness conditions. Consider an
integral primal solution $x$ and a dual solution $y$ that satisfy the
following conditions, called the {\em relaxed complementary slackness
conditions}~\cite{Vaz01}:
\[
\begin{array}{llll}
\mbox{Relaxed primal conditions:} & \forall j, \ x_j > 0 & \Rightarrow
& \ds w_j/r_1 \leq \sum_{i=1}^m a_{ij}y_i \leq w_j. \\
\mbox{Relaxed dual conditions:} & \forall i, \ y_i > 0 & \Rightarrow
&\ds b_i \leq \sum_{j=1}^n a_{ij}x_j \leq r_2 \cdot b_i.
\end{array}
\]
Then
\[
\sum_{j=1}^n w_j x_j
\leq \sum_{j=1}^n r_1 \cdot \paren{\sum_{i=1}^m a_{ij} y_i} x_j
= r_1 \cdot \sum_{i=1}^m \paren{\sum_{j=1}^n a_{ij} x_j} y_i
\leq r_1 \cdot r_2 \cdot \sum_{i=1}^m b_i y_i,
\]
which means that $x$ is $r_1 \cdot r_2$-approximate.
In this study we consider algorithms in which $r_1=1$, that is,
algorithms that relax only the dual complementary slackness
conditions. (Algorithms that relax the primal conditions are studied
in~\cite{FreRaw03}.) Typically, such an algorithm constructs an
integral primal solution $x$ and a feasible dual solution $y$
simultaneously. It starts with an infeasible primal solution and a
feasible dual solution (usually, $x=0$ and $y=0$). It iteratively
raises the dual solution and improves the feasibility of the primal
solution. In each iteration the dual solution is increased while
ensuring that the relaxed dual conditions are satisfied. Also, a
primal variable can be increased only if its corresponding primal
condition is obeyed.
%%%%%
\subsection{Local ratio}
Say we want to construct an $r$-approximation algorithm for a
minimization problem. A key step in the design of such an algorithm
is to establish a good lower bound $b$ on the weight of the optimal
solution. This bound can later be used in the analysis to prove that
the solution found by the algorithm is $r$-approximate by showing that
its weight is no more than $r \cdot b$. The local ratio technique
uses a ``local'' variation of this idea. In essence, the idea is to
break down the weight $w$ of the solution found by the algorithm into
a sum of ``partial weights'' $w=w_1+w_2+\cdots+w_k$, and similarly
break down the lower bound $b$ into $b=b_1+b_2+\cdots+b_k$, and to
show that $w_i \leq r \cdot b_i$ for all $i$. The breakdown of $w$
and $b$ is determined by the manner in which the solution is
constructed by the algorithm. In fact, the algorithm constructs the
solution in such a way as to ensure that such a breakdown exists.
Put differently, at the $i$th step, the algorithm ``pays'' $r \cdot
b_i$ and manipulates the problem instance so that the optimum drops by
at least $b_i$.
The local ratio technique is based on the following theorem. (The
proof is given for completeness.)
\begin{theorem}[local ratio theorem~\cite{BBFNS01}]
\label{The:LRT}
Let $(\F,w)$ be a minimization (maximization) problem, and let
$w,w_1$, and $w_2$ be weight functions such that $w = w_1 + w_2$.
Then if $x$ is $r$-approximate with respect to $(\F,w_1)$ and with
respect to $(\F,w_2)$, then $x$ is $r$-approximate with respect to
$(\F,w)$.
\end{theorem}
\unskip
\begin{proof}
Let $x^*,x_1^*,x_2^*$ be optimal solutions with respect to
$(\F,w),(\F,w_1)$, and $(\F,w_2)$, respectively. Then in the
minimization case we have
\[
w x = w_1 x + w_2 x
\leq r \cdot w_1 x_1^* + r \cdot w_2 x_2^*
\leq r \cdot (w_1 x^* + w_2 x^*)
= r \cdot w x^* \ .
\]
For the maximization case simply replace $\leq$ by $\geq$ and $r$ by
$\frac{1}{r}$.\qquad
%And, in the maximization case,
%\[
%w x = w_1 x + w_2 x
% \geq \frac{1}{r} \cdot w_1 x_1^* + \frac{1}{r} \cdot w_2 x_2^*
% \geq \frac{1}{r} \cdot (w_1 x^* + w_2 x^*)
% = \frac{1}{r} \cdot w x^* \ .
%\]
\end{proof}
Note that $\F$ can include arbitrary feasibility constraints, and not
just linear, or linear integer, constraints. Nevertheless, all
successful applications of the local ratio technique to date involve
problems in which the constraints are linear.
Usually, the local ratio theorem is used in the following manner.
Given a problem instance with a weight function $w$, we find a
nonnegative weight function $\delta \leq w$ such that every
{\em minimal} solution (with respect to set inclusion) is
$r$-approximate with respect to $\delta$. Then we recursively find a
minimal solution that is $r$-approximate with respect to $w-\delta$.
By the local ratio theorem this solution is $r$-approximate with
respect to the original weights $w$. The recursion terminates when a
minimal $r$-approximate solution can be found directly, which usually
occurs when the problem instance is an empty instance, or when the
weights have evolved to the point that the set of all zero-weight
elements constitutes a feasible (and hence optimal) solution. Note
that the scheme just described is tail recursive and can thus be
implemented iteratively rather than recursively.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{An introductory example: The Steiner tree problem}
\label{Sec:Steiner}
In this section we compare two approximation algorithms for the {\em
Steiner tree} problem, one based on the primal-dual schema and the
other on the local ratio technique. The algorithms are not new, but
they demonstrate how one usually uses both paradigms and thus help us
to identify differences and similarities between the two approaches.
Also, this example will be useful in the next section. We start with
the definition of the problem.
Given a graph $G=(V,E)$ and a nonempty set of {\em terminals} $T
\subseteq V$, a {\em Steiner tree} is a subtree of $G$ that
connects all the vertices in $T$. Given a nonnegative weight
function $w$ on the edges, the Steiner tree problem is to find a
minimum weight Steiner tree, where the weight of a tree is the total
weight of its edges. (We consider trees to be sets of edges.)
We are interested in Steiner trees that are {\em minimal} with
respect to set inclusion. Namely, a Steiner tree $F$ is minimal if $F
\setminus \set{e}$ is not a Steiner tree for every edge $e \in F$.
Observe that a Steiner tree is minimal if and only if every leaf in
the tree is a terminal. For an edge $e \in E$ we denote the number of
terminals incident to $e$, or the {\em terminal degree} of $e$, by
$\tau(e)$, i.e., $\tau(e) = \abs{e \cap T}$.
%The next lemma states that the average terminal degree of the vertices
%in a minimal Steiner tree is at least $1$ and at most $2$.
\begin{lemma}
\label{Lem:ST}
Let $F$ be a minimal Steiner tree. Then $\abs{T} \leq \sum_{e \in F}
\tau(e) \leq 2 \abs{T} - 2$.
\end{lemma}
\unskip
\begin{proof}
The first inequality follows from the fact that every terminal must
be incident to some edge in $F$. The second inequality can be
proven as follows. We pick an arbitrary terminal $r$ to be the root
of the Steiner tree. Next, we place a total of $2 \abs{T}-2$ coins
on the terminals---two coins on each terminal in $T \setminus
\set{r}$---and show that we can reassign the coins such that there
are at least $\tau(e)$ coins on each edge $e \in F$. Consider a
terminal $t \in T \setminus \set{r}$, and let $u$ be the parent of
$t$. Let $s$ be the terminal which is closest to $u$ on the path
from $u$ to $r$, and let $v$ be $s$'s child on that path. $t$
places one coin on the edge $(t,u)$ and another coin on the edge
$(v,s)$. (If $u=s$ and $v=t$, then two coins are placed on $(t,u)$.)
It is not hard to verify that, because the leaves of $F$ are
terminals, at least $\tau(e)$ coins are placed on every edge $e \in
F$.\qquad
\end{proof}
A slightly different proof of a more general claim is given
in~\cite{GoeWil97}.
\comment{
Examine an edge $e=(u,v)$, where $u$ is the child of $v$. If both $u$
and $v$ are non terminals then $\tau(e)=0$ and we are done. If $u$ is
a terminal then according to the charging scheme $u$ places $\tau(e)$
coins on $e$. If $u$ is not a terminal and $v$ is a terminal then
there exist a terminal such that $u$ is on the path from it to $r$.
%This is true because if no such terminal
%exists, then, by the minimality of $F$, $u$ must be a leaf, in
%contradiction to Observation~\ref{Obs:Leaf}.
It is not hard to see that otherwise $F$ is not minimal. Let $t$ a
terminal such that $u$ is on the path from it to $r$ and no other
terminal is on the path from $t$ to $u$. By the charging scheme $t$
places a coin one the edge $(u,v)$.
}
%%%%%
\subsection{Primal-dual}
A typical first step in the design of a primal-dual approximation
algorithm is to find a suitable formulation of the problem at hand as
a linear integer program. Indeed, we start with such a formulation of
the Steiner tree problem. We say that a subset $S \subseteq V$
{\em splits} $T$ if $\emptyset \subset S \cap T \subset T$. Let
$\splits(T)$ be the set of all subsets of $V$ that split $T$, i.e.,
$\splits(T) = \set{S : \emptyset \subset S \cap T \subset T}$. The
Steiner tree problem can be formulated by the following linear integer
program:
\begin{align}
\begin{array}{lll}
\min &\ds \sum_{e \in E} w(e) x_e & \\
\mbox{s.t.} & \ds \sum_{e \in (S,\bar{S})} x_e \geq 1 & \forall S \in \splits(T), \\
& x_e \in \bit & \forall e \in E,
\end{array}
\tag{ST}
\end{align}
where $(S,\bar{S})$ denotes the set of edges having exactly one
endpoint in $S$. We get an LP-relaxation by replacing the last set of
constraints by $x_e \geq 0$ for all $e \in E$. The corresponding
dual program is
\[
\begin{array}{llll}
& \max & \ds
\sum_{S \in \splitsf(T)} y_S
& \\
& \mbox{s.t.} & \ds
\sum_{S: e \in (S,\bar{S})} y_S \leq w(e)
& \forall e \in E, \\
& & y_S \geq 0
& \forall S \in \splits(T).
\end{array}
\]
\looseness=-1Algorithm~\textbf{PD-ST} is a primal-dual approximation algorithm for
the Steiner tree problem (see Figure \ref{alg1}). It is a specific implementation of the
generic algorithm from~\cite{GoeWil95b}. The algorithm starts with
$\abs{V}$ components---each containing a single vertex. The
components are induced by the solution $F$. In the $\ell$th iteration
it raises the dual variables that correspond to components that split
$T$ until some dual constraint becomes tight. Then an edge that
corresponds to some tight dual constraint is added to $F$, and the
components are updated accordingly. This process terminates when all
terminals are in the same component. Then $F$ is turned into a
minimal Steiner tree using reverse deletion.
\enlargethispage{6pt}
\begin{figure}
\begin{algorithm}{\textbf{PD-ST}$(G,w)$.}
\lyne $F \leftarrow \emptyset$
\lyne $y \leftarrow 0$
\lyne $\C_0 \leftarrow \set{\{v\} : v \in V}$
\lyne $\ell \leftarrow 0$
\pause
\lyne While $\exists C \in \C_\ell$ such that $C$ splits $T$
\lyne \> $\ell \leftarrow \ell + 1$
\lyne \> Increase $y_C$ uniformly for every $C \in \C$ that splits $T$
\cont \> until some dual constraint becomes tight
\lyne \> Let $e_\ell=(u,v)$, such that $u \in C_i$ and $v \in C_j$,
\cont \> be an edge that corresponds to a tight dual constraint
\lyne \> $F \leftarrow F \cup \{e_\ell\}$
\lyne \> $\C_\ell \leftarrow \C_{\ell-1} \cup
\set{C_i \cup C_j} \setminus \set{C_i,C_j}$
\pause
\lyne For $j \leftarrow \ell$ down-to $1$
\lyne \> If $F \setminus \set{e_j}$ is feasible
then $F \leftarrow F \setminus \set{e_j}$
\pause
\lyne Output $F$
\end{algorithm}
\vskip-8pt
\caption{}\label{alg1}
\end{figure}
First, we show that Algorithm~\textbf{PD-ST} produces feasible
solutions. Consider a solution $F$ returned by the algorithm.
Observe that all the terminals are in the same component; otherwise
the algorithm would not have terminated. Also, due to lines~11--12
$F$ is a minimal Steiner tree.
\enlargethispage*{8pt}
We need only prove that Algorithm~\textbf{PD-ST} produces
$2$-approximate solutions. Let $y$ be the dual solution corresponding
to a solution $F$ that was output by the algorithm. By the weak
duality theorem $\sum_{S \in \splitsf(T)} y_S \leq \opt$.
%$\sum_{e \in F} w(e)$.
Thus, in order to show that $F$ is $2$-approximate, it is enough to
prove that $\sum_{e \in F} w(e) \leq 2 \cdot \sum_{S \in
\splitsf(T)} y_S$.
In the $\ell$th iteration the algorithm raises $y_C$ for every
component $C$ that splits $T$, and therefore
\[
\sum_{S \in \splitsf(T)} y_S =
\sum_{\ell=1}^t \epsilon_\ell \abs{\C'_\ell},
\]
where $\epsilon_\ell$ is the dual increase at the $\ell$th iteration,
and $\C'_\ell \subseteq \C_\ell$ is the set of components that split
$T$ ({\em active} components in the terminology of~\cite{GoeWil95b}).
On the other hand, only edges that correspond to tight dual
constraints are taken into the solution $F$, and hence
\[
\sum_{e \in F} w(e)
= \sum_{e \in F} \sum_{S: e \in (S,\bar{S})} y_S
= \sum_{e \in F}
\sum_{S: e \in (S,\bar{S})}
\sum_{\ell: S \in \C'_\ell} \epsilon_\ell
= \sum_{\ell=1}^t \epsilon_\ell
\sum_{C \in \C'_\ell} \abs{(C,\bar{C}) \cap F} \ .
\]
Thus, it is enough to prove that for every $\ell \in
\set{1,\ldots,t}$,
\[
\sum_{C \in \C'_\ell}
\abs{(C,\bar{C}) \cap F} \leq 2 \cdot \abs{\C'_\ell} \ .
\]
Observe that for a component $C \in \C'_\ell$, $\abs{(C,\bar{C}) \cap
F}$ is the number of edges in $F$ with one endpoint in $C$. If we
could prove that $\abs{(C,\bar{C}) \cap F} \leq 2$ for every $C \in
\C'_\ell$, then we are done. However, this is not necessarily true.
Instead, we prove an ``amortized'' version of this claim. That is, we
prove that the average number of edges in $F$ with one endpoint in a
component $C \in \C'_\ell$ is no more that two. We remark that by
doing that we actually prove that the relaxed dual complementary
slackness conditions are satisfied (as shown in the next section).
Consider the $\ell$th iteration, and define a multigraph (a graph
that may contain multiple edges between pairs of vertices)
$G^\ell=(V^\ell,E^\ell)$ as follows. Each vertex in $V^\ell$
corresponds to a component $C \in \C_\ell$. We refer to a vertex $u$
as a terminal in $G^\ell$ if the corresponding component in $G$
contains at least one terminal (i.e., if the corresponding component
is in $\C'_\ell$). We denote the set of terminals in $G^\ell$ by
$T^\ell$. Let $u$ and $v$ be vertices in $G^\ell$ and let $C_u$ and
$C_v$ be the corresponding components. $E^\ell$ contains a copy of
the edge $(u,v)$ for every edge $(x,y) \in E$ such that $x \in C_u, y
\in C_v$, and the weight of this copy is $w(x,y)$. Consider the set
of edges $F^\ell$ that is induced by $F$ in $G^\ell$. Clearly,
\[
\sum_{C \in \C'_\ell} \abs{(C,\bar{C}) \cap F}
= \sum_{v \in T^\ell} \abs{E^\ell(v) \cap F^\ell}
= \sum_{e \in F^\ell} \tau_{G^\ell}(e),
\]
where $E^\ell(v)$ is the set of edges incident on $v$ (in $G^\ell$).
We claim that $F^\ell$ is a minimal Steiner tree in $G^\ell$. To see
this observe that in the $\ell$th iteration the terminals in each
component $C$ are connected in $G$ (by edges within each component).
Moreover, due to the reverse deletion phase (lines~11--12) the edges in
$F^\ell$ form a minimal Steiner tree in $G^\ell$.
%We claim that $F^\ell$ is a minimal Steiner tree in $G^\ell$.
%Suppose it is not. Then there exists an edge $e \in F^\ell$
%that can be removed. Thus, the corresponding edge in $F$ is redundant
%as well, in contradiction to the minimality of $F$.
Thus, by Lemma~\ref{Lem:ST}, we know that
\[
\sum_{e \in F^\ell} \tau_{G^\ell}(e)
\leq 2 \cdot |T^\ell| - 2
= 2 \cdot |C'_\ell| - 2
\]
and we are done.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Local ratio}
The following local ratio approximation algorithm (see Figure \ref{alg2}) appeared
in~\cite{Bar00} (though in less detail). In the course of its
execution, the algorithm modifies the graph by performing {\em edge
contractions}. Contracting an edge $(u,v)$ consists of ``fusing''
its two endpoints $u$ and $v$ into a single (new) vertex $z$. The
edge connecting $u$ and $v$ is deleted and every other edge incident
on $u$ or $v$ becomes incident on $z$ instead. In addition, if either
$u$ or $v$ are terminals, then $z$ is a terminal too.
\begin{figure}[t]
\begin{algorithm}{\textbf{LR-ST}$(G,T,w)$.}
\lyne If $G$ contains only one terminal then return $\emptyset$
\pause
\lyne Else:
\lyne \> Let $\epsilon = \min_e \set{w(e) / \tau(e)}$
\lyne \> Define the weight function $\delta(e) = \epsilon \cdot \tau(e)$
\lyne \> Let $e$ be an edge such that $w(e)=\delta(e)$
\lyne \> Let $(G',T')$ be the instance obtained by contracting $e$
\lyne \> $F' \leftarrow$ \textbf{LR-ST}$(G',T',w-\delta)$
\lyne \> If $F'$ is not feasible then return $F = F' \cup \set{e}$
\lyne \> Else, return $F = F'$
\end{algorithm}
\vskip-8pt
\caption{}\label{alg2}
\end{figure}
Note the slight abuse of notation in line~7. The weight function in
the recursive call is not $w-\delta$ itself, but rather the
restriction on $G'$. We will continue to silently abuse notation in
this manner.
We prove by induction on the number of terminals that
Algorithm~\textbf{LR-ST} returns a minimal Steiner tree. At the
recursion basis the solution returned is the empty set, which is both
feasible and minimal. For the inductive step, by the inductive
hypothesis, $F'$ is a minimal Steiner tree with respect to $G'$ and
$T'$. Since we add $e$ to $F$ only if we have to, $F$ is a minimal
Steiner tree with respect to $G$ and $T$.
It remains to prove that Algorithm~\textbf{LR-ST} produces
$2$-approximate solutions. The proof is also by induction on the
number of terminals. In the base case the solution returned is the
empty set, which is optimal. For the inductive step, by the inductive
hypothesis, $F'$ is $2$-approximate with respect to $G',T'$, and
$w-\delta$. Since $(w-\delta)(e)=0$, the weight of $F$ with respect
to $w-\delta$ equals that of $F'$, and the optimum value for $G,T$
with respect to $w-\delta$ cannot be smaller than the optimum value
for $G',T'$, because if $F^*$ is an optimal solution for $G,T$, then
$F^* \setminus \set{e}$ is a feasible solution of the same weight for
$G',T'$. Thus, $F$ is $2$-approximate with respect to $G,T$, and
$w-\delta$. By Lemma~\ref{Lem:ST}, any minimal Steiner tree in $G$ is
$2$-approximate with respect to $\delta$. Thus, by the local ratio
theorem, $F$ is $2$-approximate with respect to $G,T$, and $w$ as
well.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Primal-dual vs.~local ratio}
Algorithms~\textbf{PD-ST} and~\textbf{LR-ST} represent many algorithms
in the literature in the sense that each of them can be viewed as a
standard use of the corresponding paradigm. Algorithm~\textbf{PD-ST}
relies heavily on LP-duality. It is based on a predetermined linear
program and its dual program, and its analysis is based on the
comparison between the values of an integral primal solution and a
dual solution. Algorithm~\textbf{PD-ST} is iterative, and in each
iteration the dual solution is changed. In a sense, the dual solution
can be viewed as the bookkeeper of the algorithm. On the other hand,
Algorithm~\textbf{LR-ST} does not use linear programming. Instead, it
relies upon weight decompositions and a local ratio theorem. As in
this case, local ratio algorithms are typically recursive, and in each
recursive call the weights are decomposed and the instance is
modified. The decomposition is determined by a weight function
defined in the current recursive call. Thus, at least at first
glance, the two algorithms and their analyses seem very different.
Having said all that, we turn to the similarities between the
algorithms. Both algorithms use the same combinatorial property
(Lemma~\ref{Lem:ST}) to achieve an approximate solution. The
performance ratio of both algorithms was proven locally. That is, it
was shown, using the above-mentioned property, that in each
iteration/decomposition a certain ratio holds. Also, both solutions
use a reverse deletion phase. In the next section we show that this
is no coincidence. The equivalence between the paradigms is based on
the fact that ``good'' valid inequalities are equivalent to ``good''
weight functions. We shall also see that the changes in the dual
during a primal-dual algorithm are strongly connected to the values of
$\epsilon$ that are chosen in the recursive calls of a local ratio
algorithm.
%Another point worth mentioning is this. In the analysis of
%Algorithm~\textbf{PD-ST} Lemma~\ref{Lem:ST} was used to prove that the
%average number of edges that cross a component in $\C_\ell$ is no more
%that two, while in the analysis of Algorithm~\textbf{LR-ST} it was
%used in a more direct manner to show that any minimal Steiner tree is
%$2$-approximate with respect to $\delta$. In the next section we show
%that the amortized analysis of Algorithm~\textbf{PD-ST} is not
%necessary if one adds certain constraints to the linear program.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Covering problems}
\label{Sec:Cover}
Perhaps the most famous covering problem is the {\em set cover}
problem. In this problem we are given a collection of sets
$\C=\{S_1,\ldots,S_m\}$ and a weight function $w$ on the sets. The
objective is to find a minimum-weight collection of sets that
{\it covers} all elements. In other words, a collection $\C'
\subseteq \C$ is a {\em set cover} if each element in
$\bigcup_{i=1}^m S_i$ is contained in some set from $\C'$, and we aim
to find a set cover of minimum weight. Consider a set cover $\C'$.
Clearly, if we add sets from $\C \setminus \C'$ to $\C'$, the resulting
collection is also a set cover. This property is shared by all
{\em covering problems}. A minimization problem $(\F,w)$ is called
a covering problem if (1) $x \in \bit^n$, and (2) any extension of a
feasible solution to any possible instance is always feasible. In
this case, we call the set of constraints $\F$ {\em monotone}. Note
that a monotone set of linear constraints typically contains
inequalities with nonnegative coefficients.
The family of covering problems contains a broad range of optimization
problems. Many of them, such as {\em vertex cover}, {\em feedback
vertex set}, and {\em Steiner tree}, were studied extensively. In
fact, both the primal-dual schema and the local ratio technique were
developed for the purpose of finding good approximate solutions for
the {\em set cover} problem and its special case, the {\em vertex
cover} problem.
Primal-dual approximation algorithms for covering problems
traditionally reduce the size of the instance at hand in each
iteration by adding an element $j \in \set{1,\ldots,n}$ whose
corresponding dual constraint is tight to the primal solution (see,
e.g.,~\cite{GoeWil97,BerTeo98}). Local ratio algorithms for covering
problems implicitly add all zero-weight elements to the solution and,
therefore, reduce the size of the instance in each step as well (see,
e.g.,~\cite{Bar00}). In order to implement this we alter the problem
definition by adding a set (or vector), denoted by $z$, which includes
elements that are considered (at least, temporarily) to be taken into
the solution. This makes it easier to present primal-dual algorithms
recursively and to present local ratio algorithms in which the
addition of zero-weight elements to the partial solution is explicit.
More formally, given a monotone set of constraints $\F$, a weight
function $w$, and a vector $z \in \bit^n$, we are interested in the
following problem. Find a vector $x \in \bit^n$ such that (1) $z \cap
x = \emptyset$, (2) $x \cup z$ satisfies $\F$, and (3) $x$ minimizes the
inner product $w \cdot x$. (When $z=\emptyset$ we get the original
problem $(\F,w)$.) $z$ can be viewed as an additional monotone
constraint, and therefore this problem is a covering problem. The
definitions of a feasible solution, an optimal solution, and an
$r$-approximate solution can be understood in a straightforward
manner. We denote the set of feasible solutions with respect to $\F$
and $z$ by $\sol(\F,z)$. Also, a feasible solution $x$ is called
{\em minimal} (with respect to set inclusion) if for all $j \in x$
the vector $z \cup x \setminus \set{j}$ is not feasible.
We remark that the use of this terminology is very useful in the
context of this paper, i.e., for presenting generic algorithms, and
for showing the equivalence between the two paradigms. However, it
may be inept at constructing an approximation algorithm for a
specific problem.
%%%%%
\subsection{A primal-dual framework for covering problems}
\label{Sub:PDcov}
In this section we present a recursive primal-dual framework for
approximating covering problems that is based on the one by Bertsimas
and Teo~\cite{BerTeo98}.
%Many primal-dual algorithms in the literature follow the outline of
%the generic algorithm given by Goemans and Williamson~\cite{GoeWil97}.
However, before doing so we show that the framework
from~\cite{BerTeo98} extends the generic algorithm of Goemans and
Williamson~\cite{GoeWil97}. The proof of this claim is based on the
observation that every advancement step of an approximation algorithm
that uses the primal-dual schema can be represented by a change in a
single dual variable. Note that this was not shown explicitly
in~\cite{BerTeo98} and was also mentioned by Williamson~\cite{Wil02}.
The reason we show this explicitly is twofold. First, we would like
to draw attention to the fact that most primal-dual algorithms in the
literature do not follow the framework from~\cite{BerTeo98}, and
therefore their analyses are unnecessarily complicated and do not
offer much insight into the design process of the algorithm. (This is
in contrast to local ratio analyses.) Second, we want to make the
role of the complementary slackness conditions in primal-dual analyses
more apparent.
We start by presenting the algorithm of Goemans and
Williamson~\cite[p.~158]{GoeWil97}; see Figure \ref{alg3}. The algorithm and its analysis are
included for completeness. Goemans and Williamson base their generic
algorithm on the {\em hitting set} problem. In this problem we are
given a collection of subsets $T_1,\ldots,T_q$ of a ground set $E$ and
a weight function $w: E \rightarrow \reals_+$. Our goal is to find a
minimum weight subset $x \subseteq E$ such that $x \cap T_i \neq
\emptyset$ for every $i \in \set{1,\ldots,q}$. In turns out that many
known problems (shortest path, vertex cover, etc.~) are special cases
of the hitting set problem. The hitting set problem can be formulated
as follows:
\[
\begin{array}{lll}
\min & \ds \sum_{e \in E} w_e x_e & \\
\mbox{s.t.} & \ds \sum_{e \in T_i} x_e \geq 1 & \forall i \in \set{1,\ldots,q}, \\
& x_e \in \bit & \forall e \in E,
\end{array}
\]
where $x_e=1$ if and only if $e \in x$. The LP-relaxation and the
corresponding dual program are
\[
\begin{array}{cc}
\begin{array}{llll}
& \min &\ds \sum_{e \in E} w_e x_e & \\
& \mbox{s.t.} &\ds \sum_{e \in T_i} x_e \geq 1 & \forall i \in \set{1,\ldots,q}, \\
& & x_e \geq 0 & \forall e \in E,
\end{array}
&
\begin{array}{llll}
& \max & \ds \sum_{i=1}^q y_i & \\
& \mbox{s.t.} & \ds \sum_{i: e \in T_i} y_i \leq w_e & \forall e \in E, \\
& & y_i \geq 0 & \forall i \in \set{1,\ldots,q}.
\end{array}
\end{array}
\]
\begin{figure}[t]
\begin{algorithm}{GW.}
\lyne $y \leftarrow 0$
\lyne $x \leftarrow \emptyset$
\lyne $j \leftarrow 0$
\pause
\lyne While $x$ is not feasible
\lyne \> $j \leftarrow j+1$
\lyne \> $\V_j \leftarrow \mbox{\textsc{Violation}}(x)$
%\lyne \> Construct an $r$-effective set $\V_l$
\lyne \> Increase $y_k$ uniformly for all $T_k \in \V_j$
\cont \>\> until $\exists e_j \not\in x:$
$\sum_{i : e_\ell \in T_i} y_i = w_{e_j}$
\lyne \> $x \leftarrow x \cup \set{e_j}$
\lyne $\ell \leftarrow j$
\pause
\lyne For $j \leftarrow \ell$ down-to $1$
\lyne \> If $x \setminus \set{e_j}$ is feasible
then $x \leftarrow x \setminus \set{e_j}$
\pause
\lyne Output $x$
\end{algorithm}
\vskip-8pt
\caption{}\label{alg3}
\end{figure}
The algorithm starts with the feasible dual solution $y=0$ and the nonfeasible
primal solution $x = \emptyset$. It iteratively increases
the primal and dual solutions until the primal solution becomes
feasible. In each iteration, if $x$ is not feasible, then there exists
a set $T_k$ such that $x \cap T_k = \emptyset$. Such a subset is
called {\em violated}. Indeed, the increase of the dual solution
involves some dual variables corresponding to violated sets.
Specifically, the increase of the dual variables depends on a {\em
violation oracle} (called \textsc{Violation}). In each iteration
the violation oracle supplies a collection of violated subsets $\V_j
\subseteq \set{T_1,\ldots,T_q}$, and the dual variables that
correspond to subsets in $\V_j$ are increased {\em simultaneously and
at the same speed}.%
\footnote{Some subsets in $\V_j$ may not be violated.
See~\cite{GoeWil97} for more details.}
%
When $x$ becomes feasible a {\em reverse delete step} is performed.
This step removes as many elements as possible from the primal
solution $x$ as long as $x$ remains feasible.
Let $x^f$ denote the set output by the algorithm, and let $\epsilon_j$
denote the increase of the dual variables corresponding to $\V_j$.
Thus, $y_i = \sum_{j : T_i \in \V_j} \epsilon_j$, $\sum_{i=1}^q y_i =
\sum_{j=1}^\ell \abs{\V_j} \epsilon_j$, and
\begin{align*}
w(x^f)
& = \sum_{e \in x^f} w_e \\
& = \sum_{e \in x^f} \sum_{i : e \in T_i} y_i \\
& = \sum_{i=1}^q \abs{x^f \cap T_i} y_i \\
& = \sum_{i=1}^q \abs{x^f\cap T_i} \sum_{j : T_i \in \V_j} \epsilon_j \\
& = \sum_{j=1}^\ell
\left( \sum_{T_i \in \V_j} \abs{x^f \cap T_i} \right) \epsilon_j.
\end{align*}
Therefore, the weight of $x^f$ is at most $r$ times the value of the
dual solution $y$ (and, therefore, $x^f$ is $r$-approximate) if for all $j
\in \set{1,\ldots,\ell}$
\begin{eqnarray}
\label{Eqn:V}
\sum_{T_i \in \V_j} \abs{x^f \cap T_i} \leq r \cdot \abs{\V_j}.
\end{eqnarray}
Examine iteration $j$ of the reverse deletion step. We know that when
$e_j$ was considered for removal, no element $e_{j'}$ with $j' < j$
had already been removed. Thus, after $e_j$ is considered for removal,
the temporary solution is $x^j = x^f \cup \set{e_1,\ldots,e_{j-1}}$.
Observe that $x^j$ is feasible and $x^j \setminus \set{e}$ is not
feasible for all $e \in x^j \setminus \set{e_1,\ldots,e_{j-1}}$.
$x^j$ is called a {\em minimal augmentation} of
$\set{e_1,\ldots,e_{j-1}}$ in~\cite{GoeWil97}. Moreover,
\[
\sum_{T_i \in \V_j} \abs{x^f
\cap T_i} \leq \sum_{T_i \in \V_j} \abs{x^j \cap T_i} \ .
\]
%This is true for all minimal augmentations of
%$\set{e_1,\ldots,e_{j-1}}$.
Thus, to obtain bound~(\ref{Eqn:V}) Goemans and Williamson~\cite{GoeWil97}
set the following requirement on every collection of subsets
$\V_j$: $\sum_{T_i \in \V_j} \abs{x \cap T_i} \leq r \cdot \abs{\V_j}$
for any minimal augmentation $x$ of $\set{e_1,\ldots,e_{j-1}}$.
To summarize, in order to construct an $r$-approximate solution, in
each iteration of the algorithm, we seek a collection $\V$ such that
$\sum_{T_i \in \V} \abs{x \cap T_i} \leq r \cdot \abs{\V}$ for any
minimal augmentation $x$ of the current (nonfeasible) primal solution
denoted by $z$. In essence we seek a collection $\V$ that satisfies a
sort of amortized relaxed version of the dual complementary slackness
conditions. We now formalize this demand from a collection of
violated subsets in our terminology.
\begin{definition}
\label{Def:GW}
A collection $\V \subseteq \set{T_1,\ldots,T_q}$ is called
{\em $r$-effective} with respect to $(\F,w,z)$ if $\sum_{T_i \in \V}
\abs{x \cap T_i} \leq r \cdot \abs{\V}$ for any minimal feasible
solution $x$ with respect to $(\F,z)$.
\end{definition}
As did Bertsimas and Teo~\cite{BerTeo98} we prefer to speak in terms
of inequalities. An inequality is referred to as {\em valid} if any
feasible solution to the problem at hand satisfies this inequality.
For example, given an integer programming formulation of a problem, any inequality that
appears in this formulation is valid. The following definition uses
terms of inequalities and extends the previous definition.
\begin{definition}
\label{Def:BT}
A set of valid inequalities $\{\alpha^1 x \geq \beta^1,\ldots,
\alpha^k x \geq \beta^k\}$ is called {\em $r$-effective} with
respect to $(\F,w,z)$ if $\alpha^k_j=0$ for every $k$ and $j \in z$,
and any integral minimal feasible solution $x$ with respect to
$(\F,z)$ satisfies $\sum_{i=1}^k \alpha^i x \leq r \cdot \sum_{i=1}^k
\beta^i$.
If this is true for {\rm any} integral feasible solution, the set is
called {\em fully $r$-effective}.
If an $r$-effective set contains a single inequality, we refer to this
inequality as {\em $r$-effective}.
\end{definition}
We remark that we require $\alpha^k_j=0$ for every $k$ and every $j
\in z$ since in general we discuss inequalities with respect to
$(\F,z)$ and not with respect to $\F$. If $z=\emptyset$, we sometimes
say that the set (or the inequality) is $r$-effective with respect to
$\F$.
An $r$-effective collection $\V$ can be understood as the
$r$-effective set of valid inequalities $\{\sum_{e \in T_i} x_e \geq 1
: T_i \in \V \}$. However, Definition~\ref{Def:GW} allows the use of
other kinds of inequalities, and therefore extends
Definition~\ref{Def:BT}. Thus, it would seem that our goal is to find
an $r$-effective set of valid inequalities in each iteration.
However, we show that it is enough to construct a {\it single}
$r$-effective valid inequality for that purpose. Consider an
$r$-effective set $S=\{\alpha^1 x \geq \beta^1,\ldots,\alpha^k x \geq
\beta^k\}$ and the inequality that we get by summing up the
inequalities in $S$:
\[
\sum_{i=1}^k \alpha^i x
= \sum_{j=1}^n \left(\sum_{i=1}^k \alpha^i\right)_j x_j
\geq \sum_{i=1}^k \beta^i.
\]
Since $S$ is $r$-effective we know that $\sum_{i=1}^k \alpha^i x \leq
r \cdot \sum_{i=1}^k \beta^i$, and we have found our $r$-effective
inequality. Thus, our goal, in each iteration of the algorithm, is to
find an inequality $\alpha x \geq \beta$ such that any minimal
solution satisfies the following relaxed dual condition:
\[
y_i > 0 \ \Longrightarrow \ \alpha \cdot x \leq r \beta \ .
\]
For example, examine the $2$-approximation algorithm for the Steiner
tree problem (Algorithm~\textbf{PD-ST} of section~\ref{Sec:Steiner}).
The $r$-effective collection of sets that is chosen by the algorithm
in the $\ell$th iteration is $\V = \{(C,\bar{C}) \,:\, C \in
\C'_\ell\}$. The corresponding $r$-effective collection of valid
inequalities is $S=\{\sum_{e \in (C,\bar{C})} x_e \geq 1 \,:\, C \in
\C'_\ell\}$. Consider the inequality that we get by summing up the
inequalities in $S$:
\begin{equation}
\label{Eqn:EQ}
\sum_{C \in \C'_\ell} \sum_{e \in (C,\bar{C})} x_e
= \sum_{e \in E^\ell} \tau_{G^\ell}(e) x_e
\geq \abs{\C'_\ell},
\end{equation}
where $E^\ell$ is the edge set of $G^\ell$. Clearly,
(\ref{Eqn:EQ}) is valid and, by Lemma~\ref{Lem:ST}, is
also $2$-effective. Notice that the coefficients of
(\ref{Eqn:EQ}) and the weights that are used in
Algorithm~\textbf{LR-ST} are identical. As we shall see in what follows,
this is no coincidence.
Bertsimas and Teo~\cite{BerTeo98} proposed a generic algorithm to
design and analyze primal-dual approximation algorithms for problems
of the following type:
\[
\begin{array}{ll}
\min & w x \\
\mbox{s.t.} & A x \geq b, \\
& x \in \bit^n,
\end{array}
\]
where $A,b$, and $w$ are nonnegative. This algorithm
%(see Appendix~\ref{App:BT})
constructs a single valid inequality in each iteration and uses it to
modify the current instance. The size of the problem instance is
reduced in each iteration, and therefore the algorithm terminates
after no more than $n$ iterations. The approximation ratio of this
algorithm depends on the choice of the inequalities. In fact, it
corresponds to what Bertsimas and Teo call the {\em strength} of the
inequalities. In our terminology, the {\em strength} of an inequality
is the minimal value of $r$ for which it is $r$-effective. It is
important to note that, unlike other primal-dual algorithms, this
algorithm constructs new valid inequalities during its execution.
Another difference is that it uses the weight vector in order to
measure the tightness of the dual constraints. Thus, in each
iteration it decreases the weights according to the inequality that
was used. In fact, this study was inspired by the similarity between
this weight decrease and its local ratio counterpart.
Algorithm~\textbf{PDcov} is a recursive version of the algorithm
from~\cite{BerTeo98}; see Figure \ref{alg4}. The initial call is
\textbf{PDcov}$(\emptyset,w,1)$. (The third parameter is used for
purposes of analysis.) Informally, it can be viewed as follows:
construct an $r$-effective inequality; update the corresponding dual
variable and $w$ such that $w$ remains nonnegative; find an element
$j$ whose weight is zero; add $j$ to the temporary partial solution
$z$; then recursively solve the problem with respect to $\F,z$ and the
new weights (the termination condition of the recursion is met when
the empty set becomes feasible); finally, $j$ is added to the solution
$x$ only if it is necessary.
\begin{figure}[t]
\begin{algorithm}{\textbf{PDcov}$(z,w,k)$.}
\lyne If $\emptyset \in \sol(\F,z)$ return $\emptyset$
\pause
\lyne Construct a valid inequality $\alpha^k x \geq \beta^k$
\cont \> which is $r$-effective w.r.t. $(\F,z)$
\lyne $y_k \leftarrow \max \set{\epsilon \,:\, w - \epsilon \alpha^k \geq 0}$
\lyne Let $j \not\in z$ be an index for which $w_j = y_k \alpha^k_j$
\lyne $x \leftarrow$ \textbf{PDcov}$(z \cup \set{j},w - y_k \alpha^k,k+1)$
\lyne If $x \not\in \sol(\F,z)$ then $x \leftarrow x \cup \set{j}$
\pause
\lyne Return $x$
\end{algorithm}
\vskip-8pt
\caption{}\label{alg4}
\end{figure}
The following analysis is based on the corresponding analysis
from~\cite{BerTeo98}.
We start by proving by induction on the recursion that
Algorithm~\textbf{PDcov} returns minimal feasible solutions with
respect to $(F,z)$. At the recursion basis the solution returned is
the empty set, which is both feasible and minimal. For the inductive
step, let $x'$ be the solution returned by the recursive call in
line~5. $x'$ is feasible with respect to $(\F,z \cup \{j\})$ by the
inductive hypothesis; therefore $x$ is feasible with respect to
$(F,z)$. We show that $x \setminus \{i\}$ is not feasible for every
$i \in x$. For the case where $i \neq j$, if $x \setminus \{i\}$ is
feasible with respect to $(\F,z)$, then $x' \setminus \{i\}$ is
feasible with respect to $(\F,z \cup \{j\})$ in contradiction with the
minimality of $x'$. The case where $i=j$, which is relevant only when
$x=x' \cup \{j\}$, is trivial.
Next we show that the algorithm returns $r$-approximate solutions.
Consider the following linear program
\begin{align}
\begin{array}{lll}
\min & w x & \\
\mbox{s.t.} & \alpha^k x \geq \beta^k & k \in \set{1,\ldots,t}, \\
& x \geq 0,
\end{array}
\tag{P}
\end{align}
where $\alpha^k x \geq \beta^k$ is the inequality used in the $k$th
recursive call, and $t+1$ is the recursion depth.
The dual is
\begin{align}
\begin{array}{lll}
\max & \beta y & \\
\mbox{s.t.} & \ds \sum_{k=1}^t \alpha^k_j y_k \leq w_j & j \in \set{1,\ldots,n}, \\
& y \geq 0.
\end{array}
\tag{D}
\end{align}
Examine the $k$th recursive call. Let $z^k$ be the temporary partial
solution at depth $k$. $\alpha^k x \geq \beta^k$ is a valid
inequality with respect to $(\F,z^k)$, and, therefore, it is valid
with respect to $\F$. Thus, $\sol(\F) \subseteq \sol(\mbox{P})$, and
$\opt(\mbox{P}) \leq \opt(\F,w)$. As we have seen before, $x$ is a
feasible solution for $\F$ and, therefore, for (P). Also, $y$ is a
feasible solution for the dual of (P).
Let $x^k$ be the solution returned by the $k$th recursive call. Also,
let $w^k$ be the weight vector, and let $j$ be the chosen element at
the $k$th call. We prove by induction that $w^k x^k \leq r \sum_{l
\geq k} y_l \beta^l$. First, for $k=t+1$, we have
%
$w^{t+1} x^{t+1} = 0 = \sum_{l \geq t+1} y_l \beta^l$. For $k \leq t$
we have
\begin{eqnarray}
w^k x^k & = & (w^{k+1} + y_k \alpha^k) x^k
\nonumber \\
& = & w^{k+1} x^{k+1} + y_k \alpha^k x^k
\label{Eqn:PDcovstep1} \\
& \leq & r \sum_{l \geq k+1} y_l \beta^l + y_k r \beta^k
\label{Eqn:PDcovstep2} \\
& = & r \sum_{l \geq k} y_l \beta^l,
\nonumber
\end{eqnarray}
where (\ref{Eqn:PDcovstep1}) is due to the fact that $w^{k+1}_j=0$,
and (\ref{Eqn:PDcovstep2}) is implied by the induction hypothesis and
the $r$-effectiveness of the inequality $\alpha^k x \geq \beta^k$.
Finally, $x$ is $r$-approximate since
\[
w x = w^1 x^1
\leq r \sum_{l \geq 1} y_l \beta^l
\leq r \cdot \opt(\mbox{P})
\leq r \cdot \opt(\F,w) \ .
\]
We remark that the value of $y_k$ depends on the coefficients of the
valid inequality $\alpha^k x \geq \beta$. That is, we can use the
valid inequality $\rho \cdot \alpha^k x \geq \rho \cdot \beta$ for
any $\rho>0$ instead of using $\alpha^k x \geq \beta$, provided that
the value of $y_k$ is divided by $\rho$. In fact, by choosing the
appropriate value of $\rho$, we can always ensure that $y_k=1$. This
fact is used in what follows.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{A local ratio framework for covering problems}
\label{Sec:LR}
As was demonstrated in section~\ref{Sec:Steiner} the typical step of a
local ratio algorithm involves the construction of a ``good'' weight
function. Algorithm~\textbf{LR-ST} used a weight function such that
any minimal Steiner tree is $2$-approximate with respect to it.
In~\cite{Bar00} Bar-Yehuda defined this notion of goodness in the
context of covering. The definition is given in our terminology.
\begin{definition}[see \cite{Bar00}]
Given a covering problem $(\F,w,z)$, a weight function $\delta$ is
called {\em $r$-effective} with respect to $(\F,z)$ if for all $j
\in z, \delta_j=0$, and if every minimal feasible solution $x$ with
respect to $(\F,z)$ satisfies $\delta x \leq r \cdot
\opt(\F,\delta,z)$.
\end{definition}
We prefer the following equivalent (yet more practical) definition.
\begin{definition}
Given a covering problem $(\F,w,z)$, a weight function $\delta$ is
called {\em $r$-effective} with respect to $(\F,z)$ if for all $j
\in z, \delta_j=0$, and if there exists $\beta$ such that every minimal
feasible solution $x$ with respect to $(\F,z)$ satisfies $\beta \leq
\delta \cdot x \leq r \beta$. In this case we say that $\beta$ is a
{\em witness} to $\delta$'s $r$-effectiveness.
If this is true for {\rm any} integral feasible solution $\delta$
is called {\em fully $r$-effective}.
\end{definition}
We remark that we require $\delta_j=0$ for every $j \in z$ since in
general we deal with inequalities with respect to $(\F,z)$ and not
with respect to $\F$. If $z=\emptyset$, we say that $\delta$ is
$r$-effective with respect to $\F$.
Obviously, by assigning $\beta = \delta x^*$, where $x^*$ is an
optimal solution, we get that the first definition implies the latter.
For the other direction, notice that $\beta \leq \delta x^*$.
%(or $\beta \geq \delta x^*$).
A local ratio algorithm for a covering problem works as follows.
First, construct an $r$-effective weight function $\delta$ such that
$\delta \leq w$ and there exists some $j$ for which $w_j =
\delta_j$. Such a weight function is called {\em $w$-tight}.
Subtract $\delta$ from the weight function $w$. Add all zero-weight
elements to the partial solution $z$. Then recursively solve the
problem with respect to $(\F,w-\delta,z)$. When the empty set becomes
feasible (or when $z$ becomes feasible with respect to $\F$) the
recursion terminates. Finally, remove unnecessary elements from the
temporary solution by performing a reverse deletion phase.
Algorithm~\textbf{LRcov} is a generic approximation algorithm for
covering problems; see Figure \ref{alg5}. (The initial call is
\textbf{LRcov}$(\emptyset,w)$.) The main difference between the
algorithm from~\cite{Bar00} and the one given here is that in the
latter the augmentation of the temporary solution is done one element
at a time. By doing this we have the option not to include zero-weight
elements which do not contribute to the feasibility of the
partial solution $z$. When using the algorithm from~\cite{Bar00} such
elements are removed during the reverse deletion phase (called {\em
removal loop} in~\cite{Bar00}). In order to simulate the algorithm
from~\cite{Bar00}, when using Algorithm~\textbf{LRcov} we can add zero
weight elements one by one. This is due to the fact that $\delta=0$
is $r$-effective for all $r \geq 1$.
\begin{figure}[t]
\begin{algorithm}{LRcov$(z,w)$.}
\lyne If $\emptyset \in \sol(\F,z)$ return $\emptyset$
\pause
\lyne Construct a $w$-tight weight function $\delta$
\cont \> which is $r$-effective w.r.t. $(\F,z)$
\lyne Let $j \not\in z$ be an index for which $\delta_j = w_j$
\lyne $x \leftarrow$ LRcov$(z \cup \set{j},w - \delta)$
\lyne If $x \not\in \sol(\F,z)$ then $x \leftarrow x \cup \set{j}$
\pause
\lyne Return $x$
\end{algorithm}
\vskip-8pt
\caption{}\label{alg5}
\end{figure}
Proving that Algorithm~\textbf{LRcov} returns minimal feasible
solutions with respect to $(\F,z)$ is essentially identical to proving
that Algorithm~\textbf{PDcov} returns minimal feasible solutions (see
section~\ref{Sub:PDcov}). Thus, we need only to prove that
Algorithm~\textbf{LRcov} outputs an $r$-approximate solution.
We prove by induction on the recursion that Algorithm~\textbf{LRcov}
returns an $r$-approximation with respect to $(\F,w,z)$. At the
recursion basis, $\emptyset$ is an optimal solution. Otherwise, for
the inductive step, examine $x$ at the end of the recursive call. By
the induction hypothesis $x \setminus \set{j}$ is an $r$-approximation
with respect to $(\F,w-\delta,z \cup \set{j})$. Moreover, due to the
fact that $w_j-\delta_j=0$, $x$ is $r$-approximate with respect to
$(\F,w-\delta,z)$. Finally, by the $r$-effectiveness of $\delta$ and
the local ratio theorem we get that $x$ is an $r$-approximate solution
with respect to $(\F,w,z)$ as well.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Equivalence}
\label{Sec:Equiv}
It is not hard to see that Algorithm~\textbf{PDcov} and
Algorithm~\textbf{LRcov} share the same structure. Both algorithms,
in each recursive call, modify the weights, add a zero-weight element
to $z$, and solve the problem recursively.
%(Indeed, the proofs that
%both supply a feasible minimal solution are the same.)
The only difference between the two is that Algorithm~\textbf{PDcov}
uses $r$-effective inequalities, while Algorithm~\textbf{LRcov}
constructs $r$-effective weight functions. The following lemma shows
that an $r$-effective valid inequality and an $r$-effective weight
function are one and the same.
\begin{lemma}
\label{Lem:Equiv}
$\alpha x \geq \beta$ is an $r$-effective inequality if and only if
$\alpha$ is an $r$-effective weight function with $\beta$ as a
witness.
\end{lemma}
\unskip
\begin{proof}
Let $\alpha x \geq \beta$ be an $r$-effective inequality. By
definition every minimal feasible solution $x$ satisfies $\beta \leq
\alpha x \leq r \beta$. Thus, $\alpha$ is an $r$-effective weight
function. On the other hand, let $\alpha$ be an $r$-effective weight
function with a witness $\beta$. Due to the $r$-effectiveness of
$\alpha$ every minimal feasible solution $x$ satisfies $\beta \leq
\alpha x \leq r \beta$. Therefore, $\alpha x \geq \beta$ is an
$r$-effective inequality.\qquad
\end{proof}
We remark that when using an $r$-effective weight function $\delta$,
Algorithm~\textbf{LRcov} does not need to know the value of the
witness to $\delta$'s $r$-effectiveness. In fact, it can be NP-hard
to calculate this value. The same goes for Algorithm~\textbf{PDcov}.
We do not have to know the value of the right-hand side of an $r$-effective
inequality $\alpha x \geq \beta$. This is demonstrated in
section~\ref{Sub:FVS}.
By Lemma~\ref{Lem:Equiv} the use of an inequality can be
simulated by utilizing the corresponding weight function, and vice
versa. Thus, the primal-dual schema and the local ratio technique
converge on standard applications.
\begin{corollary}
\label{Cor:Equiv}
Algorithms~\textbf{PDcov} and~\textbf{LRcov} are identical. Moreover,
the equivalence is constructive; i.e., any implementation of one can
be transformed into an implementation of the other.
\end{corollary}
Although both algorithms are equivalent, the analysis of
Algorithm~\textbf{PDcov} seems more complicated than the analysis of
Algorithm~\textbf{LRcov}. The difference is artificial. The local
ratio technique uses a {\em local} approach. A typical local ratio
advancement step is local in the sense that it can be analyzed
independently of the rest of the algorithm (see also~\cite{Bar00}).
Therefore, local ratio algorithms tend to be recursive and their
analyses inductive. On the other hand, primal-dual analyses use a
more {\em global} approach. Instead of comparing intermediate
weights, the total weight of the integral primal solution is compared
to the cost of the dual solution. This approach is also used outside
the primal-dual schema (e.g.,~\cite{JaiVaz01,JMMSV03}). The
equivalence implies that there is no need to use the global approach
in the context of the primal-dual schema. Indeed, the analysis of
Algorithm~\textbf{PDcov} uses exactly the same local arguments as the
analysis of Algorithm~\textbf{LRcov}.
In the analysis of Algorithm~\textbf{PDcov} we compared the integral
primal solution $x$ to a dual solution $y$ in order to prove that the
former is $r$-approximate. Recall that $y$ was not a dual solution to
the original program. We have defined a new program, called (P), that
contains the valid inequalities that were used by the algorithm, and
the primal solution was compared to the dual of (P). Clearly, the best
approximation ratio we can hope for using this approach is the
{\em integrality gap} of (P). Thus, one can check whether an
analysis for an algorithm is tight by comparing the performance ratio
given by the analysis to the integrality gap of (P). Now, consider the
set of weight functions that were used by an implementation of
Algorithm~\textbf{LRcov}. The corresponding inequalities would be the
constraints of (P). Thus, one can check whether an analysis of a local
ratio algorithm is tight by calculating the integrality gap of (P) as
well.
%In~\cite{BerTeo98} Bertsimas and Teo define the notion of
%{\em strength}. In our terminology the strength of an inequality
%is the minimum $r$ for which it is $r$-effective. They show that if
%one uses an inequality of strength $\lambda$, then an
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Applications}
\label{Sec:Examples}
%While the frameworks contain guidelines to design and analyze
%algorithms, both do not generate approximation algorithms
%'automatically'.
When trying to approximate a minimization problem we need to address
several issues that depend on the combinatorial structure of the
problem at hand. First and foremost, we need to construct valid
$r$-effective inequalities, or $r$-effective weight functions. Also,
we need to use them such that the algorithm terminates in polynomial
time. The algorithms for covering problems make use of the fact that
you can add a zero-weight element to the temporary partial solution
and, by doing so, reduce the size of the problem. This ensures that the
running time is polynomial. Also, this allows us to use inequalities
or weight functions which are $r$-effective with respect to the
current instance, but are not necessarily so with respect to the original
instance. Many covering problems were approximated by making use of
this mechanism (e.g., feedback vertex set~\cite{BBF99} and network
design problems~\cite{GoeWil97}). This is demonstrated in what follows.
Namely, we illustrate how Algorithms~\textbf{PDcov} and~\textbf{LRcov}
can be used to construct and analyze approximation algorithms for
covering problem. Note that when an algorithm is presented it is not
given in full detail. We only describe the valid inequalities or
weight functions needed in order to implement it using one of the
generic algorithms.
Many approximation algorithms for covering problems use only one type
of inequality or weight function. Such algorithms rely on the fact
that when an instance is modified (or when an element is added to $z$,
in our terminology) the resulting instance is still an instance of the
same covering problem. For example, when Algorithm~\textbf{LR-ST}
contracts an edge the resulting instance is still an instance of the
{\em Steiner tree} problem. Bertsimas and Teo~\cite{BerTeo98} call
an integer programming formulation that satisfies this property {\em reducible}.
Thus, in such cases, it is enough to describe and analyze an
inequality or a weight function with respect to the original set of
constraints $\F$.
%%%%%
\subsubsection{Steiner tree and other network design problems}
Let $\F$ be a set of constraints for the {\em Steiner tree} problem
(e.g., the inequalities in (ST)). Consider the instance
$(\F,z)$ for some vector $z$. Recall that the elements (i.e., edges)
in $z$ are assumed to be taken into the solution. Thus, an instance
$(\F,z)$ contains components on which there are connectivity demands.
Bearing this in mind it is not hard to see that
Algorithm~\textbf{LR-ST} (see Figure \ref{alg2}) is an
implementation of Algorithm~\textbf{LRcov}. In each recursive call
the algorithm uses the weight function $\delta(e)= \epsilon \cdot
\tau(e)$, where $\epsilon = \min_e \set{w(e)/\tau(e)}$, and then
contracts a zero-weight edge. (Recall that $\tau(e)$ is the number of
terminals incident to $e$.) This contraction can be represented by
adding the edge $e$ to $z$.
While Algorithm~\textbf{LR-ST} can be viewed as an implementation of
Algorithm~\textbf{LRcov}, Algorithm~\textbf{PD-ST} is not an
implementation of Algorithm~\textbf{PDcov}. For starters
Algorithm~\textbf{PD-ST} is iterative and not recursive. Also, it
raises several dual variables in each iteration, and not one.
However, as demonstrated in section~\ref{Sub:PDcov}, when summing up
the inequalities that correspond to the dual variables that are raised
in an iteration, we get (\ref{Eqn:EQ}), which is
$2$-effective. Therefore, it is enough to raise a single dual
variable corresponding to (\ref{Eqn:EQ}) in each recursive
call of Algorithm~\textbf{PDcov}.
Algorithm~\textbf{PD-ST} is a special case of an algorithm for
{\em constrained forest} problems given by Goemans and
Williamson~\cite{GoeWil95b}. Given a graph $G=(V,E)$, a function
$f:2^V \rightarrow \bit$, and a nonnegative weight function $w$ on
the edges, they have considered the integer program
\[
\begin{array}{lll}
\min & \ds \sum_{e \in E} w_e x_e & \\
\mbox{s.t.} & \ds \sum_{e \in \delta(S)} x_e \geq f(S)
& \forall S, \ \emptyset \subset S \subset V, \\
& x_e \in \bit & \forall e \in E,
\end{array}
\]
where $\delta(S)$ denotes the set of edges having exactly one endpoint
in $S$. They presented a $(2-2/\abs{A})$-approximation
algorithm, where $A=\set{v : f(v)=1}$, for the case where $f$ is {\em
proper}.%
\footnote{A function $f$ is {\em proper} if (1) for all $S \subset V,
\ f(S) = f(V \setminus S)$; and (2) for all $S, T, \ S \cap T =
\emptyset, \ f(S \cup T) \leq \max\set{f(S),f(T)}$.}
%
In~\cite{GoeWil97} Goemans and Williamson showed that the same
algorithm outputs a $2$-approximate solution in the case of
{\em downwards monotone} functions.%
\footnote{A function $f$ is {\em downwards monotone} if $f(S)=1$
implies $f(S')=1$ for all nonempty $S' \subseteq S$.}
%
Williamson et al.~\cite{WGMV95} generalized this algorithm for
the class of {\em uncrossable} functions.%
\footnote{A function $f$ is {\em uncrossable} if (1) for all $S
\subset V, \ f(S) = f(V \setminus S)$, and (2) if $S,T$ are
intersecting sets such that $f(S) = f(T) = 1$, then either $f(S
\setminus T) = f(T \setminus S)=1$ or $f(S \cap T) = f(S \cup T) =
1$.}
%
They used this generalization to present a multiphase
primal-dual $2f_{\max}$-approximation algorithm for general proper
functions, where $f_{\max} = \max_S f(S)$. They reduced the problem
to a sequence of hitting set problems and applied the primal-dual
approximation algorithm for {\em uncrossable} functions to each
subproblem. Thus, the solution to the original problem is the union
of the solutions of the subproblems. Consequently, Goemans et
al.~\cite{GGPSTW94} improved the approximation ratio to $2
\mathcal{H}(f_{\max})$, where $\mathcal{H}$ is the harmonic function.
(For more details see~\cite{GoeWil97}.)
Bertsimas and Teo~\cite{BerTeo98} showed that (\ref{Eqn:EQ}) is
$2$-effective even when $f$ is {\em uncrossable}. Thus, all the
above algorithms can be implemented using Algorithm~\textbf{PDcov}.
Moreover, because $\tau$ is a $2$-effective weight function, all of
them can be explained by local ratio means using
Algorithm~\textbf{LRcov}. In fact, the multiphase primal-dual
algorithms from~\cite{WGMV95,GGPSTW94} can be analyzed as multiphase
local ratio algorithms. In~\cite{BBFR04} Bar-Yehuda et al.~presented
the algorithm from~\cite{GoeWil95b} in local ratio terms and, in
particular, showed that $\tau$ is $2$-effective for {\em proper} and
{\em downwards monotone} functions.
%%%%%
\subsubsection{Generalized hitting set}
The {\em generalized hitting set} problem is defined as follows.
Given a collection of subsets $S$ of a ground set $E$, a nonnegative
weight $w(s)$ for every set $s \in S$, and a nonnegative weight
$w(u)$ for every element $u \in E$, find a minimum-weight collection
of objects $C \subseteq E \cup S$, such that for all $s \in S$, either
there exists $u \in C$ such that $u \in s$ or $s \in C$. As in the
{\em hitting set} problem our objective is to hit all the sets in $S$
by using elements from $E$. However, in this case, we are allowed not
to cover a set $s$, provided that we pay a tax $w(s)$. The hitting
set problem is the special case where the tax is infinite for all
sets. The generalized hitting set problem can be formalized as
follows:
\[
\begin{array}{lll}
\min &\ds \sum_{u \in E} w(u) x_u + \sum_{s \in S} w(s) x_s & \\
\mbox{s.t.} &\ds \sum_{u \in s} x_u + x_s \geq 1 & \forall s \in S, \\
& x_t \in \bit & \forall t \in E \cup S,
\end{array}
\]
where $x_u=1$ if and only if $u$ is in the cover, and $x_s=1$ if and
only if $s$ is not hit.
Observe that paying the tax $w(s)$ is required only when $s$ is not
hit. Thus, the inequality $\sum_{u \in s} x_u + x_s \geq 1$ is a
$\Delta$-effective inequality for any set $s \in S$, where $\Delta =
\max \set{\abs{s} : s \in S}$. The corresponding $\Delta$-effective
weight function is
\[
\delta(t) =
\begin{cases}
\epsilon, & t \in \set{s} \cup s, \\
0 & \mbox{otherwise}.
\end{cases}
\]
Thus, a $\Delta$-approximation algorithm can be constructed using one
of the frameworks. We remark that the above inequalities remain
$\Delta$-effective if we use any value between $1$ and $\Delta$ as
$x_s$'s coefficient. Analogously, any value between $\epsilon$ and
$\Delta \cdot \epsilon$ is acceptable for $\delta(s)$.
A linear time $\Delta$-approximation algorithm can be obtained by
extending the $\Delta$-approximation algorithm for hitting
set~\cite{BarEve81}. Use the above inequalities (weight functions) in
an arbitrary order; then construct a zero-weight minimal feasible
solution as follows: pick all zero-weight elements and all the sets
which are not hit by some zero-weight element.
%This would be a $\Delta$-approximate solution.
When $\Delta=2$ we get a special case
called {\em generalized vertex cover}, for which Hochbaum~\cite{Hoc02}
presented an O$(nm \log n^2/m)$ $2$-approximation algorithm.
%%%%%
\subsubsection{Feedback vertex set in tournaments}
\label{Sub:FVST}
A {\em tournament} is an orientation of a complete (undirected)
graph; i.e., it is a directed graph with the property that for every
unordered pair of distinct vertices $\{u,v\}$ it either contains the
arc $(u,v)$ or the arc $(v,u)$, but not both. The {\em feedback
vertex set in tournaments} problem is the following. Given a
tournament and a weight function $w$ on its vertices, find a
minimum-weight set of vertices whose removal leaves a graph containing
no directed cycles.
It is not hard to verify that a tournament contains a directed cycle
if and only if it contains a {\em triangle}, where a triangle is a
directed cycle of length $3$. Thus, we may restrict our attention to
triangles and formulate the problem as follows:
\begin{align}
\begin{array}{lll}
\min & \ds \sum_{v \in V} w_v x_v & \\
\mbox{s.t.} &\ds \sum_{v \in T} x_v \geq 1 & \forall \mbox{ triangle } T, \\
& x_v \in \bit & \forall v \in V.
\end{array}
\tag{FVST}
\end{align}
We say that a triangle is {\em positive} if all of its vertices have
strictly positive weights. Clearly, the set of all zero-weight
vertices is an optimal solution (of zero-weight) if and only if the
tournament contains no positive triangles. Thus we obtain a
$3$-approximation algorithm by means of the following $3$-effective
weight function. Let $\{v_1,v_2,v_3\}$ be a positive triangle and
let $\epsilon=\min\{w(v_1),w(v_2),w(v_3)\}$. Define
\[
\delta(v)=
\begin{cases}
\epsilon, & v \in \{v_1,v_2,v_3\},\\
0 & \text{otherwise.}
\end{cases}
\]
The maximum cost, with respect to $\delta$, of a feasible solution is
clearly at most $3 \epsilon$, while the minimum cost is at least
$\epsilon$, since every feasible solution must contain at least one of
$v_1$, $v_2$,~$v_3$. The corresponding $3$-effective inequality is
$x_{v_1} + x_{v_2} + x_{v_3} \geq 1$.
Note that {\it any} feasible solution is $3$-approximate with
respect to $\delta$ (not only minimal solutions). Equivalently, the
inequality $x_{v_1} + x_{v_2} + x_{v_3} \leq 3$ holds for {\it any}
feasible solution. Thus, the weight function and inequality are
fully $r$-effective.
%%%%%
\subsubsection{Feedback vertex set}
\label{Sub:FVS}
A set of vertices in an undirected graph is called a {\em feedback
vertex set} if its removal leaves an acyclic graph
(i.e.,~a forest). In other words, the set must cover all cycles in
the graph. The {\em feedback vertex set} problem is as follows: given a
vertex-weighted graph, find a minimum weight feedback vertex set.
Bafna, Berman, and Fujito \cite{BBF99} presented a local ratio
$2$-approximation algorithm for the {\em feedback vertex set} problem.
Their algorithm can be implemented using Algorithm~\textbf{LRcov}. A
cycle $C$ is {\em semidisjoint} if there exists $x \in C$ such that
$\deg(u) = 2$ for every vertex $u \in C \setminus \set{x}$. If $G$
contains a semidisjoint cycle $C$, let $\epsilon = \min_{v \in C}
w(v)$, and use the $1$-effective weight function
\[
\delta_1(v)=
\begin{cases}
\epsilon, & v \in C,\\
0 & \text{otherwise};
\end{cases}
\]
otherwise use the weight function $\delta_2(v) = \epsilon
\cdot(\deg(v)-1)$, where $\epsilon = \min_{v \in V}
\set{w(v)/\right.$\break $\left.(\deg(v)-1)}$. Bafna, Berman, and Fujito \cite{BBF99} showed that
$\delta_2$ is $2$-effective in graphs that (1) do not contain
semidisjoint cycles, and (2) $\deg(v) \geq 2$ for every $v \in V$ .
In order to implement this algorithm using Algorithm~\textbf{PDcov}
one should use the following valid inequalities: $\sum_{v \in C} x_v
\geq 1$ in case $G$ contains a semidisjoint cycle $C$, and $\sum_{v
\in V} (\deg(v)-1) \cdot x_v \geq \abs{E}-\abs{V}+1$ otherwise.
Another $2$-approximation algorithm is due to Becker and
Geiger~\cite{BecGei96}. In~\cite{Bar00} Bar-Yehuda indicated that
their algorithm can be restated in local ratio terms with the weight
function $\delta(v) = \deg(v)$, which is $2$-effective. It can be
shown that the corresponding $2$-effective inequality is $\sum_{v \in
V} \deg(v) x_v \geq \abs{E}-\abs{V}+1+\tau$, where $\tau$ is the
cardinality of the smallest feedback vertex set in $G$. Therefore, a primal-dual
analysis to this algorithm can be given by using
Algorithm~\textbf{PDcov}. It is important to note that we do not need
to know the value $\tau$ in order to execute the algorithm. In fact,
this value is NP-hard to compute.
Chudak et al.~\cite{CGHW98} explained both algorithms using
primal-dual and added a third $2$-approximation algorithm which is
similar to the one from~\cite{BBF99}. We present it as an
implementation of Algorithm~\textbf{PDcov}. That is, we show which
inequality to use in each recursive call. An {\em end-block} is a
biconnected component containing at most one articulation point.
Choose an end-block $B$ and use the inequality
%
$\sum_{v \in V} (\deg(v)-1) x_v \geq \abs{E}-\abs{V}+1$. The
corresponding weight function is
\[
\delta(v)=
\begin{cases}
\epsilon\cdot(\deg(v)-1), & v \in B,\\
0 & \text{otherwise}.
\end{cases}
\]
Local ratio implementations of the three algorithms and a detailed
analysis of the one from~\cite{BecGei96} can be found
in~\cite{BBFR04}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Minimization frameworks}
\label{Sec:Min}
The recursive algorithms for covering problems can be divided into
three primitives: the recursion base, the way that an instance is
modified before a recursive call, and the way in which the solution
returned by a recursive call is fixed. In this section we present a
more general framework that can explain many algorithms that do not
fall within the scope of our generic algorithms for covering. This is
done by means of extending each of the three primitives mentioned
above.
%%%%%
%\subsection{The primitives}
\paragraph{Modifying the instance}
The frameworks for covering problems rely heavily on the fact that the
set of constraints $\F$ is monotone. In each recursive call the
current instance is modified by assuming that a zero-weight element is
taken into the solution (i.e., by adding a zero-weight element to
$z$). This can be done because in covering problems adding a
zero-weight element to the solution is never a bad move. However, in
the noncovering case, a solution containing this element may not even
exist. Also, in nonboolean problems, there are several possible
assignments for a zero-weight variable. Thus, we need to extend the
algorithms by considering more ways in which to modify the instance.
\paragraph{Fixing solutions}
After each recursive call the covering algorithms fix, if necessary,
the solution returned in order to turn it into a ``good'' solution,
i.e., into a minimal solution. This is done because the algorithms
use weight functions or inequalities that are $r$-effective. The
solution returned by the recursive call is fixed in a very
straightforward manner---add the element that was removed from the
instance to the solution if it is not feasible. It turns out that an
algorithm may use weight functions or inequalities for which good
solutions are solutions that satisfy a certain property different from
\textit{minimality}. In fact, this property can be simply {\it the
solutions returned by the algorithm}. We refer to such weight
functions and inequalities as {\em $r$-effective with respect to a
property $\Py$}. Clearly, in such cases, the algorithm may be
forced to fix the solution returned by a recursive call in a way that
is very different from simply adding a single element in case the
current solution is not feasible.
\paragraph{Recursion base}
By adding a new element to $z$ in each recursive call of
Algorithm~\textbf{LRcov} (or \textbf{PDcov}), we are bound to arrive
at the recursion base, which is the empty instance, and for which the
empty set is always a minimal optimal solution. However, other
recursion bases are possible. In~\cite{BarEve85} Bar-Yehuda and Even
developed a $(2-\frac{\log\log n}{2\log n})$-approximation algorithm
for a {\em vertex cover} which is partly based on local ratio. Their
algorithm starts with a local ratio phase that removes short odd
cycles from the graph, and then continues to the next phase that finds
approximate solutions for graphs that do not have short odd cycles.
This can be explained by a variant of Algorithm~\textbf{LRcov} in
which the recursion base is replaced by the invocation of an
approximation algorithm that works only for inputs of a certain kind
and returns $r$-approximate minimal solutions. (The solution need not
be minimal if the weight functions used are fully $r$-effective.)
\subsection{The algorithms}
Our framework can be described as follows. In each recursive call the
algorithm constructs and uses a weight function or an inequality and
modifies the instance. Then it recursively solves the problem on the
new instance and the new objective function. Afterwards, it fixes the
solution returned. The recursion base is performed if an instance
satisfies some property $\Q$.
We use the following three subroutines:
\begin{itemize}
\item \textbf{Modify}$(\F,w)$: Modifies the current instance by
assigning values to zero-weight variables and then removing them.
This subroutine modifies an instance such that any valid inequality
with respect to the modified instance is also valid with respect to
the current instance (and hence to the original instance as well).
% In most algorithms the modification involves a single zero-weight
% element. A more complicated modification is described in
% Section~\ref{Sub:Modify}.
\item \textbf{Fix}$(\F,w,x',\Py)$: Given an $r$-approximate solution
$x'$ for the instance \textbf{Modify}$(\F,w)$, returns an
$r$-approximate solution $x$ for the instance $(\F,w)$ satisfying
some property $\Py$. The solution $x$ is constructed from $x'$ by
changing only zero-weight variables. Note that each recursive call
may use a different property.
% Typically, when dealing with covering problems a solution is fixed
% by adding a zero-weight element if necessary. In cases where the
% property $\Py$ is not \textsl{minimality} the transformation may be
% somewhat more involved as demonstrated in
% Section~\ref{Sub:Property}.
\item \textbf{Base}$(\F,w)$: Given a problem instance that satisfies
$\Q$ returns an $r$-approx-\break imate solution.
% that satisfies some property $\Py$.
% Usually, we return an empty set when the instance is empty.
% However, the recursion base may be a much more complicated, as shown
% in Section~\ref{Sub:Base}.
\end{itemize}
%%%%%
This time we start with the local ratio algorithm.
%The algorithm is as follows.
\begin{figure}[t]
\begin{algorithm}{LRmin$(\F,w)$.}
\lyne If $\F$ satisfies $\Q$ return \textbf{Base}$(\F,w)$
\pause
\lyne Construct a weight function $\delta$ which is $r$-effective
with respect to
\cont a property $\Py$ such that $w-\delta \geq 0$
\lyne $\F' \leftarrow$ \textbf{Modify}$(\F,w-\delta)$
\lyne $x' \leftarrow$ \textbf{LRmin}$(\F',w-\delta)$
\lyne $x \leftarrow$ \textbf{Fix}$(\F,w-\delta,x',\Py)$
\pause
\lyne Return $x$
\end{algorithm}
\vskip-8pt
\caption{}\label{alg6}
\end{figure}
The analysis of Algorithm~\textbf{LRmin} (see Figure \ref{alg6}) is similar to the analysis of
Algorithm~\textbf{LRcov}. We prove that the algorithm returns an
$r$-approximate solution by induction on the recursion. The recursion
base is trivial since subroutine~\textbf{Base} returns $r$-approximate
solutions by definition. For the inductive step, consider the
solution $x'$ that was returned by the recursive call. By the
inductive hypothesis $x'$ is $r$-approximate with respect to
$(\F',w-\delta)$. Due to subroutines~\textbf{Modify} and~\textbf{Fix}
$x$ is $r$-approximate with respect to $(\F,w-\delta)$ and satisfies
property $\Py$. Furthermore, $\delta$ is $r$-effective with respect
to $\Py$. Thus, by the local ratio theorem $x$ is also
$r$-approximate with respect to $(\F,w)$.
%%%%%
%\subsection{Primal-dual}
Algorithm~\textbf{PDmin} (see Figure \ref{alg7}) is our primal-dual approximation algorithm.
It uses the same three primitives that are used by
Algorithm~\textbf{LRmin}.
\begin{figure}[t]
\begin{algorithm}{PDmin$(\F,w)$.}
\lyne If $\F$ satisfies $\Q$ return \textbf{Base}$(\F,w)$
\pause
\lyne Construct an inequality $\alpha x \geq \beta$
which is $r$-effective with respect to
\cont a property $\Py$ such that $w-\alpha \geq 0$
\lyne $\F' \leftarrow$ \textbf{Modify}$(\F,w-\alpha)$
\lyne $x' \leftarrow$ \textbf{PDmin}$(\F',w-\alpha)$
\lyne $x \leftarrow$ \textbf{Fix}$(\F,w-\delta,x',\Py)$
\pause
\lyne Return $x$
\end{algorithm}
\vskip-8pt
\caption{}\label{alg7}
\end{figure}
We show that Algorithm~\textbf{PDmin} returns $r$-approximate
solutions. We do that by generalizing the analysis of
Algorithm~\textbf{PDcov}. Let $t+1$ be the recursion depth. Let
$(\F_k,w^k)$ denote the instance given to the $k$th recursive call,
and let $x^k$ denote the solution returned by the $k$th recursive
call. Consider the linear program
\begin{align}
\begin{array}{lll}
\min & w x & \\
\mbox{s.t.} & \alpha^k x \geq \beta^k & k \in \set{1,\ldots,t+1}, \\
& x \geq 0,
\end{array}
\tag{P}
\end{align}
where $\alpha^k x \geq \beta^k$ for $k \in \set{1,\ldots,t}$ is the
inequality used in the $k$th recursive call, $\alpha^{t+1} = w^{t+1}$,
and $\beta^{t+1} = w^{t+1} \cdot x^{t+1}/r$. Due to
subroutine~\textbf{Modify}, and since $\alpha^{t+1} x \geq
\beta^{t+1}$ for every solution $x$, (P) is a relaxation of $\F$, and
therefore $\opt(\mbox{P}) \leq \opt(\F,w)$.
Let us build a solution $y$ to the dual of (P), that is denoted by (D).
Let (P$_k$) be the linear program that we get from (P) by discarding the first $k-1$
inequalities and changing the objective function to $w^k x$, and let
(D$_k$) be the dual of (P$_k$). Consider the base instance
$(\F_{t+1},w^{t+1})$. Subroutine~\textbf{Base} returns a solution
$x^{t+1}$ whose weight is no more than $r$ times the optimal solution
of $(\F_{t+1},w^{t+1})$. $x$ is also $r$-approximate with respect to
(P$_{t+1})$. (Note that (P$_{t+1}$) contains only one constraint.) Thus,
$w^{t+1} x^{t+1}$ is bounded by $r$ times the value of $y^*=1$ which
is an optimal solution to (D$_{t+1})$. Let $y$ be a vector of size
$t+1$ whose entries are all $1$. Let $y^k$ be the vector that
consists of $t-k+1$ $1$'s. That is, $y^k$ is a vector that contains
the last $t-k+1$ entries of $y$. We prove by induction that $y^k$ is
a solution to (D$_k$) for all $k$, which implies that $y$ is a feasible
solution of (D) (since $y = y^1$, and ($\mbox{D})=(\mbox{D}_1$)). At the
base of the recursion, $y^{t+1}=y^*$ is an optimal solution to
(D$_{t+1}$). For the inductive step, we assume that $y^{k+1}$ is a
solution to (D$_{k+1}$) and prove that $y^k$ is a solution to (D$_k$).
First, we claim that $(0,y^{k+1})$ (a vector consisting of a zero
followed by the entries of $y^{k+1}$) is a feasible solution to (D$_k$).
To see this, notice that a packing of constraints from (P$_{k+1}$) is
also a packing of constraints from (P$_k$). Thus, $y^k=(1,y^{k+1})$ is
also a packing of constraints from (P$_k$), since
$w^k=w^{k+1}+\alpha^k$.
We can now analyze the approximation ratio. We prove by induction
that $w^k x^k \leq r \sum_{l \geq k} y_l \beta^l$ for all $k$. For
$k=t+1$, this is true since $\beta^{t+1} = \alpha^{t+1} x^{t+1}/r$.
For $k \leq t$ we have
\begin{eqnarray}
w^k x^k & = & (w^{k+1} + \alpha^k) x^k
\nonumber \\
& = & w^{k+1} x^{k+1} + y_k \alpha^k x^k
\label{Eqn:PDstep1} \\
& \leq & r \sum_{l \geq k+1} y_l \beta^l +
y_k r \beta^k
\label{Eqn:PDstep2} \\
& = & r \sum_{l \geq k} y_l \beta^l, \nonumber
\end{eqnarray}
where (\ref{Eqn:PDstep1}) stems from the fact that
subroutine~\textbf{Fix} changes only zero-weight variables, and
(\ref{Eqn:PDstep2}) is due to the induction hypothesis, the fact that
subroutine~\textbf{Fix} returns solutions with property $\Py$, and the
$r$-effectiveness of the inequality $\alpha^k x \geq \beta^k$ with
respect to $\Py$. $x$ is $r$-approximate since
\[
w x = w^1 x^1
\leq r \sum_{l \geq 1} y_l \beta^l
\leq r \cdot \opt(\mbox{P})
\leq r \cdot \opt(\F,w) \ .
\]
%%%%%
\subsection{Discussion}
The only varying elements in the framework for covering are the
$r$-effective inequalities (weight functions). That is, in order to
construct an algorithm for a covering problem one has to find the
appropriate inequalities (weight functions), and the rest is determined
by the framework. The task of designing an algorithm may be much more
complicated when one chooses to use the framework given in this
section. For starters one has to come up with a suitable and
polynomial implementation of subroutines~\textbf{Base},
\textbf{Modify}, and~\textbf{Fix}. Also, the resulting algorithm must
reach the recursion base in polynomial time. Intuitively, after
finding an $r$-effective inequality (weight function), we must ask
ourselves the following question: How should we remove zero-weight
elements? We must be able to remove zero-weight elements in a way
that enables us to later fix the solution returned by the recursive
call. A good answer to this question is an implementation of
subroutines~\textbf{Modify} and~\textbf{Fix}. Note that, as in the
covering setting, our generic algorithms may use a different type of
inequality (weight function) in each recursive call. Moreover, they
may use a different property in each recursive call. However, this
may require us to implement several versions of
subroutines~\textbf{Modify} and~\textbf{Fix}. Also, when using a
nontrivial recursion base, we can look at the primal-dual (local ratio)
phase of the algorithm as a clean-up phase whose output is an instance
of a certain type that we know how to solve by
subroutine~\textbf{Base}.
The minimization frameworks can be applied to a large family of
algorithms. They can be used in cases of noncovering problems as
demonstrated in section~\ref{Sub:Modify} on {\em minimum
{\rm 2}-satisfiability}. They can be used to analyze algorithms that have
a nonstandard recursion base, such as the $(2-\frac{\log\log n}{2\log
n})$-approximation algorithm for {\em vertex cover}
from~\cite{BarEve85}, or the $2.5$-approximation algorithm for {\em
feedback vertex set in tournaments} given in section~\ref{Sub:Base}.
The frameworks can be used to explain algorithms that do not use
$r$-effectiveness with respect to {\it minimality}, and use a
nonstandard instance modification. They can also be used on problems
whose solutions are nonboolean. An algorithm using a nonstandard
instance modification that approximates a nonboolean {\em bandwidth
trading} problem is given in section~\ref{Sub:Property}. Another
example of an algorithm approximating a nonboolean problem is a
primal-dual algorithm by Guha et al.~\cite{GHKO02} for {\em
capacitated vertex cover}. A local ratio interpretation can be
found in~\cite{BBFR04}.
Another important point is that an $r$-effective weight function with
respect to a property $\Py$ and an $r$-effective inequality with
respect to $\Py$ are one and the same. This can be shown in a way
similar to the proof of Lemma~\ref{Lem:Equiv}. Thus, the equivalence
between the two paradigms that was shown with respect to algorithms
for covering problems continues to hold even in a more general
setting. Namely, Algorithms~\textbf{LRmin} and~\textbf{PDmin} are
equivalent. We note that the equivalence extends to algorithms
outside the scope of our frameworks. For example, in~\cite{BarRaw04c}
we show that the fractional local ratio technique can be explained
using primal-dual arguments.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Applications}
\label{Sec:Non}
%In this section we present algorithms that can be explained using the
%minimization frameworks.
%%%%%
\subsubsection{Feedback vertex set in tournaments}
\label{Sub:Base}
Cai, Deng, and Zang \cite{CDZ01} presented a $2.5$-approximation algorithm for
{\em feedback vertex set in tournaments} (see section~\ref{Sub:FVST}).
The algorithm is divided into two parts: a local ratio phase that
disposes of certain {\em forbidden} subtournaments, and an algorithm
that finds an optimal solution in any tournament that does not contain
these forbidden subtournaments. The forbidden subtournaments are
shown in Figure \ref{NewFig1} below (where the two arcs not shown in $T_1$ may take any
direction).
\begin{figure}[h]
\center
\includegraphics{NewFig1.eps}
\caption{}\label{NewFig1}
\end{figure}
%\[
%\begin{array}{c@{\hspace{50pt}}c}
%\psmatrix[mnode=dot,colsep=20pt,rowsep=20pt]
%a & & b \\
% & c \\
%d & & e
%\endpsmatrix
%\psset{shortput=nab,arrows=->}
%\ncline{1,1}{1,3}
%\ncline{1,3}{3,3}
%\ncline{3,3}{3,1}
%\ncline{3,1}{1,1}
%%
%\ncline{2,2}{1,1}
%\ncline{2,2}{3,3}
%\ncline{1,3}{2,2}
%\ncline{3,1}{2,2}
%&
%\psmatrix[mnode=dot,colsep=20pt,rowsep=20pt]
%a & & b \\
% & c \\
%d & & e
%\endpsmatrix
%\psset{shortput=nab,arrows=->}
%\ncline{1,1}{1,3}
%\ncline{1,3}{3,3}
%\ncline{3,3}{3,1}
%\ncline{3,1}{1,1}
%
%\ncline{2,2}{1,1}
%\ncline{2,2}{3,1}
%\ncline{1,3}{2,2}
%\ncline{3,3}{2,2}
%\ncarc[arcangle=-30]{1,1}{3,3}
%\ncarc[arcangle=-30]{3,1}{1,3}
%\\
%T_1 & T_2
%\end{array}
%\]
The
local ratio phase employs the following fully $2.5$-effective weight
function. Let $F$ be a set of five positive-weight vertices inducing
a forbidden subtournament and define
\[
\delta(v)=
\begin{cases}
\epsilon, & v \in F,\\
0 & \text{otherwise,}
\end{cases}
\]
where $\epsilon=\min_{v \in F} \set{w(v)}$. $\delta$ is fully
$2.5$-effective since the cost of every feasible solution is at most
$5 \epsilon$, whereas the minimum weight is at least $2 \epsilon$
since every set of four vertices in $F$ contains a triangle. After
removing at least one vertex from every forbidden subtournament using
local ratio, the problem can be solved optimally on the remaining
graph.
%(A detailed presentation of the local ratio part of this
%algorithm can be found in~\cite{BBFR04}.)
This algorithm can be seen as an implementation of
Algorithm~\textbf{LRmin} in which subroutines~\textbf{Modify}
and~\textbf{Fix} are standard, and subroutine~\textbf{Base} is the
algorithm that solves the problem on tournaments that do not contain
the forbidden subtournaments.
Using our primal-dual framework, this algorithm can be also analyzed
using primal-dual arguments. This can be done by using
$2.5$-effective inequalities of the form $\sum_{u \in F} x_u \geq 2$,
where $F$ is a set of five positive-weight vertices inducing a
forbidden subtournament. Clearly, these inequalities are valid with
respect to the original instance. Cai, Deng, and Zang \cite{CDZ01} show that
the integrality gap of the (FVST) (see section~\ref{Sub:FVST})
is $1$ in the case of tournaments that do not contain the forbidden
subtournaments. They actually prove the stronger claim that
in tournaments that do not contain the forbidden subtournaments,
the primal and dual programs have identical cost integral solutions.
%
%Thus, the implementation of Subroutine~\textbf{Base} satisfies
%Condition~\ref{Con:Base}.
%%%%%
\subsubsection{Minimum weight \boldmath$2$-satisfiability}
\label{Sub:Modify}
Given a $2$CNF formula $\varphi$ with $m$ clauses on the variables
$x_1,\ldots,x_n$ and a weight function $w$ on the variables, the
weight of a truth assignment $x \in \bit^n$ is $\sum_{i=1}^n w_i x_i$.
The {\em minimum weight $2$-satisfiability} problem (or min-2SAT for
short) is to find a minimum weight truth assignment $x \in \bit^n$
which satisfies $\varphi$, or to determine that no such assignment
exists. We formulate min-$2$SAT as follows:
\begin{align}
\begin{array}{lll}
\min & \ds \sum_{i=1}^n w_i x_i \\
\mbox{s.t.} & x_i + x_j \geq 1
& \forall (x_i \vee x_j) \in \varphi, \\
& x_i - x_j \geq 0
& \forall (x_i \vee \overline{x}_j) \in \varphi, \\
& - x_i - x_j \geq -1
& \forall (\overline{x}_i \vee \overline{x}_j) \in \varphi, \\
& x_i \in \bit & \forall i \in \set{1,\ldots,n}.
\end{array}
\tag{2SAT}
\end{align}
Gusfield and Pitt~\cite{GusPit92} presented an $O(mn)$ time
$2$-approximation algorithm for min-2SAT. Though they did not use
local ratio arguments explicitly, their algorithm can be easily
analyzed using local. Hochbaum et al.~\cite{HMNT93} presented a
$2$-approximation algorithm for the {\em two variables per constraint
integer programming} problem (2VIP) that generalizes min-2SAT.
Later, Bar-Yehuda and Rawitz~\cite{BarRaw01} presented a local
ratio $2$-approximation algorithm for 2VIP that is more efficient than
the algorithm from~\cite{HMNT93}. On the special case of min-2SAT
this algorithm is a variant of the Gusfield--Pitt algorithm. Note
that min-2SAT can be approximated using a reduction to vertex
cover~\cite[pp.~131--132]{Hoc97}.
First, we can check whether $\varphi$ is satisfiable by using the
algorithm from~\cite{EIS76}. Thus, we may assume that $\varphi$ is
satisfiable. In order to design a $2$-approximation algorithm we need
to construct $2$-effective inequalities. Given a literal $\ell$, let
$T(\ell)$ denote the set of variables which must be assigned $\true$
whenever $\ell$ is assigned $\true$. (Constructing $T(\ell)$ for some
literal $\ell$ can be done efficiently by using constraint
propagation.) Let $x_i,x_j$, and $x_k$ be variables such that $x_j \in
T(x_i)$ and $x_k \in T(\overline{x}_i)$. For such variables the
inequality $x_j + x_k \geq 1$ is valid. Note that one can get
inequalities of this form by summing up the appropriate inequalities
from the program~2SAT. Moreover, it is not hard to see that this
inequality is fully $2$-effective. However, instead of using these
inequalities one at a time, we can use an inequality of the form
$\sum_{x_j \in T(x_i)} a_j x_j + \sum_{x_k \in T(\overline{x}_i)} b_k
x_k \geq \beta$ where all the $a_j$'s and $b_k$'s are nonnegative and
$\beta = \sum_j a_j = \sum_k b_k$. This inequality is $2$-effective
since it is a linear combination of inequalities of the form $x_j+x_k
\geq 1$.
Let $\alpha x \geq \beta$ be such an inequality in which $\beta = \min
\{\sum_{x_j \in T(x_i)} w_j, \sum_{x_k \in T(\overline{x}_i)} w_k\}$.
Assume without loss of generality that $\sum_{x_i \in T(x_1)} w_i \leq
\sum_{x_j \in T(\overline{x}_1)} w_j$. Observe that if we subtract
$\alpha$ from the objective function, assigning $\true$ to all
literals in $T(x_i)$ is free of charge. It can be shown that this
partial assignment does not change the satisfiability of the formula.
That is, if $\varphi'$ is the formula we get by performing this
zero-weight partial assignment to the variables of a formula
$\varphi$, $\varphi'$ is satisfiable if and only if $\varphi$ is
satisfiable. After performing this instance modification the rest of
the assignment can be found recursively. The primal-dual
implementation of the algorithm is as follows. At the recursion base
we return an empty assignment on the empty formula.
%Clearly, Condition~\ref{Con:Base} is satisfied in this case.
If the formula $\varphi$ is not empty, we pick a variable $x_i$ and
construct an inequality $\alpha x \geq \beta$ as shown above. Note
that such inequalities are valid with respect to the original
instance.
%and therefore Condition~\ref{Con:Valid} is satisfied.
We call subroutine~\textbf{Modify} that in this case constructs a
zero-weight partial assignment for $\varphi$ and creates a new
formula $\varphi'$. Then we recursively solve the problem on
$\varphi'$. Afterwards, subroutine~\textbf{Fix} combines the
assignment for $\varphi'$ that was returned and the partial assignment
that was constructed by subroutine~\textbf{Modify}. For the local
ratio implementation, it is enough to notice that $\alpha$ is a
fully $2$-effective weight function. (For more details
see~\cite{BarRaw01}.)
%%%%
\subsubsection{A bandwidth trading problem}
\label{Sub:Property}
Bhatia et al.~\cite{BCFN03} studied the following {\em bandwidth
trading} problem. We are given a set of machine {\em types}
$\T=\set{T_1,\ldots,T_m}$ and a set of {\em jobs}
$J=\set{1,\ldots,n}$. Each machine type $T_i$ is defined by two
parameters: a time interval $I(T_i)$ during which it is {\em
available}, and a weight $w(T_i)$, which represents the weight of
allocating a machine of this type. Each job $j$ is defined by a
single time interval $I(j)$ during which it must be processed. We say
that job $j$ {\em contains} time $t$ if $t\in I(j)$. A given job $j$
may be {\em scheduled feasibly} on a machine of type $T$ if type $T$
is available throughout the job's interval, i.e.,~if $I(j) \subseteq
I(T)$. A {\em schedule} is a set of machines together with an
assignment of each job to one of them. It is {\em feasible} if every
job is assigned feasibly and no two jobs with intersecting intervals
are assigned to the same machine. The weight of a feasible schedule
is the total cost of the machines it uses, where the weight of a
machine is defined as the weight associated with its type. The goal
is to find a minimum-weight feasible schedule. We assume that a
feasible schedule exists. (This can be checked easily.) Bhatia et
al.~\cite{BCFN03} presented a primal-dual $3$-approximation algorithm
for this problem. A detailed local ratio analysis of their algorithm
can be found in~\cite{BBFR04}. This algorithm constructs weight
functions or inequalities that are $r$-effective weight functions with
respect to a property $\Py$ different from {\it minimality} and
modifies the solution returned by a recursive call in a rather elaborate
manner.
We present the algorithm in local ratio terms in Figure \ref{alg8}.
\begin{figure}[t]
\begin{algorithm}{BT$(\T,J,w)$.}
\lyne If $J=\emptyset$, return $\emptyset$
\pause
\lyne Let $t$ be a point in time contained in a maximum number of jobs,
\cont and let $\mathcal{T}_t$ be the set of machine
types available at time $t$
% (see Figure~\ref{Fig:BT})
\lyne Let $\epsilon= \min\set{w(T) \,:\, T\in \mathcal{T}_t}$
\lyne Define the weight function
$\delta(T)=
\begin{cases}
\epsilon, & T \in \mathcal{T}_t,\\
0 & \text{ otherwise,}
\end{cases}$
\pause[2.5]
\cont /$\ast$ Subroutine~\textbf{Modify} $\ast$/
\lyne Let $\T_t' = \set{T \,:\, T \in T_t, \ w(T)=\delta(T)}$
\lyne Let $J' = \set{j \in J \,:\, \exists T \in \T_t',
\ I(j) \subseteq I(T)}$
\pause
\lyne $S' \leftarrow \textbf{BT}(\T \setminus \T_t',
J \setminus J',w-\delta)$
\pause
\cont /$\ast$ Subroutine~\textbf{Fix} $\ast$/
\lyne Extend $S'$ to $J$ by allocating $\abs{J'}$ machines
and scheduling one
\cont job from $J'$ on each.
\cont Job $j \in J'$ is assigned to a machine of type $T \in \T_t'$
\cont such that $I(j) \subseteq I(T)$.
\lyne Transform $S'$ into a new schedule $S$ as described below
\pause
\lyne Return $S$
\end{algorithm}
\vskip-8pt
\caption{}\label{alg8}
\end{figure}
%\begin{figure}
%\begin{center}
%\input{maxclique.pstex_t}
%\end{center}
%\caption{Jobs containing time $t$ (top, dark), and machine types
% available at time $t$ (bottom, dark).}
%\label{Fig:BT}
%\end{figure}
To complete the description of the algorithm we need to describe the
transformation of $S'$ to $S$ referred to in line~9. Instead, we just
point out two facts relating to this transformation. (The details of
the transformation appear in~\cite{BCFN03} and also in~\cite{BBFR04}.)
\begin{enumerate}
\item \label{Fac:le}
For all machine types $T$, $S$ does not use more machines
of type $T$ than $S'$.
\item \label{Fac:3k}
Let $k$ be the number of jobs containing time $t$ (Line~2). The
number of machines used by $S$ whose types are in $\T_t$ is at
most $3k$.
\end{enumerate}
Based on these facts, we show that Algorithm~\textbf{BT} is a specific
implementation of Algorithm~\textbf{LRmin} that returns
$3$-approximate solutions. By fact~\ref{Fac:le}, $w'(S) \leq w'(S')$,
where $w'=w-\delta$, and therefore $S$ is $3$-approximate with
respect to $w'$. Thus, subroutines~\textbf{Modify} and~\textbf{Fix}
work as required. (Subroutine~\textbf{Base} is standard in this
case.) By fact~\ref{Fac:3k}, $\delta(S) \leq 3k \epsilon$, and
because there are $k$ jobs containing time $t$---each of which can be
scheduled only on machines whose types are in $\T_t$, and no two of
which may be scheduled on the same machine---the optimum cost is at
least $k \epsilon$. Thus, $S$ is $3$-approximate with respect to
$\delta$.
%We now turn to the primal-dual analysis.
Bhatia et al.~\cite{BCFN03} formulated the bandwidth trading
problem by the following program:
\[
\begin{array}{lll}
\min & \ds \sum_{i=1}^n w(T_i) x_i \\
\mbox{s.t.} & \ds \sum_{i} y_{ij} \geq 1
&\ds \forall j \in J,\\
& \ds x_i - \sum_{j \in J(t)} y_{ij} \geq 0
& \ds \forall T_i \in \T, \ \forall t \in E \cap I(T_i), \\
& \ds x_i \in \naturals & \forall T_i \in \T, \\
&\ds y_{ij} \in \bit & \forall T_i \in \T, j \in J,
\end{array}
\]
where
\begin{itemize}
\item $x_i$ represents the number of machines allocated of type $T_i$;
\item $y_{ij}=1$ if and only if job $j$ is assigned to machine type
$T_i$; note that $y_{ij}$ is defined only if $I(j) \subseteq
I(T_i)$, where $i$ is of type $T$;
\item $E$ is the set of endpoints of job intervals;
\item $J(t) = \set{j \,:\, t \in I(j)}$.
\end{itemize}
In order to transform Algorithm~\textbf{BT} into a primal-dual
algorithm, we use the inequality $\delta \cdot x \geq k \epsilon$.
%Similarly to the local ratio case,
It is not hard to verify that
%can be shown that
this version of Algorithm~\textbf{BT} is an implementation of
Algorithm~\textbf{PDmin}. The above inequality is valid with respect
to the original instance, since if there are $k$ jobs whose interval
contains time $t$, then at least $k$ machines whose types belong to
$T_t$ must be allocated.
We remark that our primal-dual analysis is slightly different from the
analysis in~\cite{BCFN03}. Specifically, their algorithm uses similar
but not identical inequalities that can be described as linear
combinations of inequalities from the above formulation.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Maximization problems}
\label{Sec:Max}
Bar-Noy et al.~\cite{BBFNS01} developed constant factor approximation
algorithms for various resource allocation and scheduling problems
using local ratio. They also presented primal-dual algorithms for
these problems. This was the first time a local ratio or primal-dual
approximation algorithm for a natural maximization problem was
presented. In this section we present two equivalent generic
approximation algorithms for maximization problems that can be used to
analyze the algorithms from~\cite{BBFNS01}. We demonstrate this on
one of the problems that was discussed in~\cite{BBFNS01} called {\em
interval scheduling}. Also, we show that our generic algorithms can
explain the exact optimization (or $1$-approximation) algorithm for
the {\em longest path in a DAG} problem.
%%%%%
\subsection{The frameworks}
Before describing the generic algorithms, we address the issue of
$r$-effectiveness in the context of maximization. We discuss the
issue in terms of weight functions, but a similar discussion can be
made in terms of inequalities. Recall that $\delta$ is $r$-effective
with respect to a property $\Py$ if there exists $\beta$ such that
$\beta \leq \delta x \leq r \beta$ for every solution $x$ that
satisfies $\Py$. In the maximization setting it is more convenient to
consider the following equivalent definition. $\delta$ is
$r$-effective with respect to a property $\Py$ if there exists $\beta$
such that $\frac{\beta}{r} \leq \delta x \leq \beta$ for every
solution $x$ that satisfies $\Py$. Clearly any feasible solution that
satisfies $\Py$ is $r$-approximate with respect to $\delta$.
Our frameworks are recursive and work as follows. If the instance is
empty, then return the empty set. Otherwise, construct a weight
function (inequality) that is $r$-effective with respect to some
property $\Py$. Subtract the weight function (coefficients of
inequality) from the objective function. Remove some of the
nonpositive-weight elements from the instance. (The decision of which
element to remove depends on the problem at hand. Algorithms for {\em
packing} problems usually remove all nonpositive-weight elements.)
Then recursively solve the problem with respect to the new instance
and weights. Upon returning from the recursive call, the solution
returned is fixed such that it satisfies $\Py$.
%The weight function
%(inequality) is built in a way that ensures the ability to fix the
%solution returned by the recursive call.
%
We remark that in order to simplify the presentation our maximization
algorithms are not as general as our minimization algorithms. Namely,
they use a limited version of subroutine~\textbf{Modify} that simply
removes some nonpositive-weight elements from the instance and do
not use a version of subroutine~\textbf{Base} at all. We also limit
our discussion in this section to sets of feasibility constraints $\F$
for which $x \in \set{0,1}^n$.
We start with our local ratio approximation algorithm for maximization
problems\break ---Algorithm~\textbf{LRmax} (see Figure \ref{alg9}). The initial call is
\textbf{LRmax}$(\set{1,\ldots,n},w)$. A recursive call of
Algorithm~\textbf{LRmax} considers the instance that is induced by the
set of elements $N$ that corresponds to the set of positive-weight
elements. It starts with the construction of a weight function
$\delta$. Then a recursive call is made on the instance that is
induced by the objective function $w-\delta$ and the set $N \setminus
\N$, where $\N$ is a set that contains nonpositive-weight elements
with respect to $w-\delta$. Subroutine~\textbf{Fix} is used to fix
the solution returned by adding only zero-weight elements with respect
to $w-\delta$. The resulting solution satisfies property $\Py$.
\begin{figure}[t]
\begin{algorithm}{LRmax$(N,w)$.}
\lyne If $N = \emptyset$, return $\emptyset$
\lyne Construct a weight function $\delta$ which is $r$-effective
\cont \> with respect to $(\F,N)$ and $\Py$
\lyne Let $\N \subseteq \set{j \,:\, w_j - \delta_j \leq 0}$
\lyne $x' \leftarrow \textbf{LRmax}(N \setminus \N,w - \delta)$
\lyne $x \leftarrow \mbox{\textbf{Fix}}(\F,w-\delta,x,\Py)$
\lyne Return $x$
\end{algorithm}
\vskip-8pt
\caption{}\label{alg9}
\end{figure}
We prove by induction that Algorithm~\textbf{LRmax} returns an
$r$-approximate solutions with respect to $(N,w)$. In the base case,
$\emptyset$ is an optimal solution. For the inductive step, examine
$x$ at the end of the recursive call. By the induction hypothesis
$x'$ is $r$-approximate with respect to $(N \setminus \N,w-\delta)$.
Moreover, since $w_j-\delta_j \leq 0$ for every $j \in \N$, $x$ is
$r$-approximate with respect to $(N,w-\delta)$. (Recall that
subroutine~\textbf{Fix} adds only zero-weight elements with respect to
$w-\delta$.) Finally, $x$ satisfies $\Py$ due to
subroutine~\textbf{Fix}; therefore by the $r$-effectiveness of
$\delta$ with respect to $\Py$ and by the local ratio theorem, we get
that $x$ is $r$-approximate with respect to $(N,w)$ as well.
Algorithm~\textbf{PDmax} (see Figure \ref{alg10}) is very similar to Algorithm~\textbf{LRmax}.
Obviously, Algorithm~\textbf{PDmax} uses inequalities instead of
weight functions. Also, as in the minimization case, we assume that
the inequalities that are used by the algorithm are valid with respect
to the original set of constraints $\F$. This condition is imperative
to the construction of a feasible dual solution.
\begin{figure}[t]
\begin{algorithm}{PDmax$(N,w)$.}
\lyne If $N = \emptyset$, return $\emptyset$
\lyne Construct a valid inequality $\alpha^k x \leq \beta^k$
which is $r$-effective
\cont \> with respect to $(\F,N)$ and $\Py$
\lyne Let $\N \subseteq \set{j \,:\, w_j - \alpha_j \leq 0}$
\lyne $x' \leftarrow \textbf{PDmax}(N \setminus \N,w - \alpha)$
\lyne $x \leftarrow \mbox{\textbf{Fix}}(\F,w-\alpha,x,\Py)$
\lyne Return $x$
\end{algorithm}
\vskip-8pt
\caption{}\label{alg10}
\end{figure}
We show that Algorithm~\textbf{PDmax} returns $r$-approximate
solutions. Let notation with subscript $k$ denote the appropriate
object in the $k$th iteration, and let $t+1$ be the recursion depth.
Consider the linear program
\begin{align}
\begin{array}{lll}
\min & w x & \\
\mbox{s.t.} & \alpha^k x \leq \beta^k & k \in \set{1,\ldots,t}, \\
& x \geq 0,
\end{array}
\tag{P}
\end{align}
where $\alpha^k x \leq \beta^k$ is the inequality used in the $k$th
recursive call. Every feasible solution satisfies the constraints in
(P), namely, $\sol(\F) \subseteq \sol(\mbox{P})$. Thus, $x \in
\sol(\mbox{P})$ and $\opt(\mbox{P}) \geq \opt(\F,w)$.
\enlargethispage{12pt}
Consider the dual of (P):
\begin{align}
\begin{array}{lll}
\min & \ds \sum_{k=1}^t \beta^k y_k & \\
\mbox{s.t.} &\ds \sum_{k=1}^t \alpha^k_j y_k \geq w_j & j \in \set{1,\ldots,n}, \\
& y \geq 0.
\end{array}
\tag{D}
\end{align}
We claim that $y=(1,\ldots,1)$ is a feasible solution to (D). To do
that we conceptually add the following between line~2 and line~3: $y_k
\leftarrow 1$. Clearly, the resulting dual solution is
$y=(1,\ldots,1)$. In terms of the dual solution, elements leave the
set $N$ only when their corresponding dual constraint is satisfied.
Algorithm~\textbf{PDmax} terminates when the current instance is
empty, namely, when $N=\emptyset$. Therefore, at termination all dual
constraints are satisfied.
We prove by induction that $w^k x^k \geq \frac{1}{r} \sum_{l \geq k}
y_l \beta^l$. At the induction basis, $0 = w^{t+1} x^{t+1} \geq
\frac{1}{r} \sum_{l \geq t+1} y_l \beta^l = 0$. For $k \leq t$ we
have
\begin{equation*}
w^k x^k = (w^{k+1} + \alpha^k) x^k
= w^{k+1} x^{k+1} + y_k \alpha^k x^k
\geq \frac{1}{r} \cdot \sum_{l \geq k+1} y_l \beta^l +
\frac{\beta^k}{r}
= \frac{1}{r} \cdot \sum_{l \geq k} y_l \beta^l,
\end{equation*}
where the second equality is due to the fact that
subroutine~\textbf{Fix} uses only zero-weight elements, and the
inequality is implied by the induction hypothesis and the
$r$-effectiveness of the $k$th inequality. Therefore, $w x = w^1 x^1
\geq \frac{1}{r} \sum_{l \geq 1} y_l \beta^l \geq \frac{1}{r} \cdot
\opt(\mbox{P}) \geq \frac{1}{r} \cdot \opt(\F,w)$.
Notice that the maximization case is different from the minimization
case. In the latter we keep the weights nonnegative, while in the
former, weights are allowed to be negative. Moreover, the objective
function in the maximization case is expected to be nonpositive when
the algorithm terminates. This means, in primal-dual terms, that the
dual solution is initially not feasible, and its feasibility is
improved during the execution of the algorithm. Also, at termination,
the negative entries of the weight function correspond to the
nontight dual constraints. This difference makes life more
complicated in the maximization setting. Speaking in local ratio
terms, in the minimization case, the weight function $\delta$ is
constructed such that it satisfies two conditions: (1) $\delta \leq
w$, and (2) there exists an element $j$ for which $w_j = \delta_j$.
In the maximization case, the second condition is satisfied but the
first is not. In fact, given an $r$-effective weight function
$\delta$, it is not always clear by which factor $\epsilon>0$ we
should multiply it before subtracting it from the objective function.
We are allowed to increase $\epsilon$ as long as the solution returned
by the recursive call can be fixed using only zero-weight elements.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Applications}
\label{Sec:MaxExamples}
%In this section we present algorithms that can be analyzed using the
%maximization frameworks.
%%%%%
\subsubsection{Interval scheduling}
\label{Sub:IS}
As mentioned before, in~\cite{BBFNS01} Bar-Noy et al. presented local
ratio approximation algorithms for several resource allocation and
scheduling problems that can be explained by our frameworks. We
demonstrate this by analyzing one of the algorithms
from~\cite{BBFNS01} that approximates a problem called {\em interval
scheduling}. Bar-Noy et al. also presented primal-dual algorithms for
the same problems. However, in order to do so they modified the
original algorithms. We show that there is no need to change the
algorithms in order to supply a primal-dual analysis.
In the interval scheduling problem we are given a set of
{\em activities}, each requiring the utilization of a given
{\em resource}. The activities are specified as a collection of
sets $\A_1,\ldots,\A_m$. Each set represents a single activity: it
consists of all possible {\em instances} of that activity. An
instance $I \in \A_i$ is defined by the following parameters:
\begin{enumerate}
\item A half-open time interval $[s(I),e(I))$ during which the activity
will be executed. $s(I)$ and $e(I)$ are called the
{\em start-time} and {\em end-time} of the instance.
\item The weight $w(I) \geq 0$ gained by scheduling this instance
of the activity.
\end{enumerate}
A {\em schedule} is a collection of instances. It is feasible if
it contains at most one instance of every activity and at most one
instance for all time instants $t$. In the interval scheduling
problem our goal is to find a schedule that maximizes the total weight
accrued by instances in the schedule.
The interval scheduling problem can be formulated by means of an
integer program on the boolean variables $\set{x_I : I \in
\A_i, 1 \leq i \leq m}$.
\[
\begin{array}{lll}
\max & \ds \sum_I w(I) x_I & \\
\mbox{s.t.} &\ds \sum_{I : s(I) \leq t < e(I)} x_I \leq 1
& \ \forall t, \\
& \ds \sum_{I : I \in \A_i} x_I \leq 1
& \ \forall i \in \set{1,\ldots,m}, \\
& x_I \in \bit
& \ \forall i \ \forall I \in A_i.
\end{array}
\]
The $2$-approximation algorithm for interval scheduling
from~\cite{BBFNS01} can be viewed as an application of
Algorithm~\textbf{LRmax}. In order to describe it as such, we need to
show (1) how to construct a weight function $\delta$ that is
$2$-effective with respect to some property $\Py$; (2) which elements
are removed from the instance (i.e., which elements are taken into
$\N$); and (3) how to fix the solution returned by the recursive call
(i.e., describe subroutine~\textbf{Fix}). Let $\tI$ be an instance
with minimum end-time, and let $\A(\tI)$ and $\I(\tI)$ be the activity
to which instance $\tI$ belongs and the set of instances intersecting
$\tI$ (including $\tI$), respectively. (See Figure~\ref{Fig:IS}.)
Define
\[
\delta(I) =
\begin{cases}
w(\tI), & I \in \A(\tI) \cup \I(\tI), \\
0 & \text{otherwise.}
\end{cases}
\]
We show that $\delta$ is $2$-effective with respect to some property
$\Py$. We say that a feasible schedule $S$ is $\tI$-maximal if either
it contains $\tI$ or $\tI$ cannot be added to $S$ without rendering it
infeasible. It is not hard to verify that the weight of every
$\tI$-maximal schedule with respect to $\delta$ is at least $w(\tI)$
and no more than $2 \cdot w(\tI)$. (Notice that a feasible schedule
contains no more than two instances from $\A(\tI) \cup \I(\tI)$.)
Now, the elements that are taken into $\N$ are all nonpositive
elements with respect to $w-\delta$. Finally, we describe
subroutine~\textbf{Fix}. Let $S'$ be the schedule returned by the
recursive call. If $S' \cup \{\tI\}$ is a feasible solution, return
$S= S' \cup \{\tI\}$. Otherwise, return $S=S'$. Clearly, $S$ is
$\tI$-maximal.
\begin{figure}
\begin{center}
\input{interval.pstex_t}
\end{center}
\caption{%
\label{Fig:IS}%
$\tI, \A(\tI), \I(\tI)$: heavy lines represent $A(\tI)$,
dashed lines represent $\I(\tI)$.}
\end{figure}
As mentioned before, Bar-Noy et al.~\cite{BBFNS01} also presented
primal-dual algorithms that are slightly different from their local
ratio algorithms. In terms of the interval scheduling problem they
modified the original algorithm by using a different $2$-effective
weight function:
\[
\delta'(I) =
\begin{cases}
w(\tI), & I = \tI, \\
\half w(\tI), & I \in \A(\tI) \cup \I(\tI) \setminus \{\tI\}, \\
0 & \text{otherwise.}
\end{cases}
\]
The corresponding inequality is $\half \sum_{I \in \I(\tI)} x_I +
\half \sum_{I \in A(\tI)} x_I \leq 2$. Note that this inequality is a
linear combination of two inequalities from the above integer program.
The original algorithm can be explained by the $2$-effective
inequality $\sum_{I \in \I(\tI) \cup \A(\tI)} x_I$\break $\leq 2$. The
difference between $\delta$ and $\delta'$ (or between their
corresponding inequalities) is the ratio between the weight of $\tI$
and the weights of the other instances in $\A(\tI) \cup \I(\tI)$. In
fact, any value between $1$ and $2$ is acceptable.
%%%%%
\subsubsection{Longest path in a DAG}
The {\em longest path} problem is as follows: given an arc-weighted directed
graph $G=(V,A)$ and two distinguished vertices $s$ and $t$, find a
simple path from $s$ to $t$ of maximum {\em length}, where the
{\em length} of a path is defined as the sum of weights of its
arcs. For general graphs (either directed or undirected) the problem
is NP-hard~\cite{GarJoh79}, but for {\em directed acyclic graphs}
(DAGs) it is solvable in linear time by a Dijkstra-like algorithm that
processes the nodes in topological order. The problem of finding the
longest path in a DAG (also called the {\em critical path}) arises in
the context of PERT (Program Evaluation and Review Technique) charts.
For more details see~\cite[p.~538]{CLR90}
or~\cite[pp.~138--142]{Eve79}.
We show that the above-mentioned linear time algorithm can be seen as
an implementation of Algorithms~\textbf{LRmax} and~\textbf{PDmax}. We
allow negative arc weights, and we assume that every vertex is
reachable from $s$. (Otherwise, simply delete all vertices that are
unreachable from $s$.) We also assume that the vertices of $G$ were
topologically sorted, and that $t$ is the last vertex in this
topological sort. Instead of solving the original problem we solve
the following more general problem. Namely, instead of searching for
a longest path from $s$ to $t$ we would like to find the longest path
from some vertex in a set $S$ to $t$ without using arcs within $S$.
In the original problem $S=\set{s}$. Also, if $s \in S$ and for all
$u \in S$ the longest path from $s$ to $u$ is of length zero, then the
problem is equivalent to the original problem.
Consider a cut $(S,\bar{S})$ such that $s \in S$, $t \in \bar{S}$, and
there is no arc leaving $\bar{S}$ and entering $S$. Note that if we
take the first $k$ vertices in the topological sort, we get such a cut.
We define the following function:
\[
\delta(e) =
\begin{cases}
\epsilon, & e \in S \times \bar{S}, \\
0 & \text{otherwise.}
\end{cases}
\]
Clearly, any path from $s$ to $t$ must cross the cut $(S,\bar{S})$
exactly once, and thus $\delta$ is fully $1$-effective. Equivalently, the
equality $\sum_{e \in S \times \bar{S}} x_e = 1$ is valid. Having
defined a suitable weight function or equality, we continue with a
description of the algorithm. We describe a recursive call of the
algorithm using local ratio terms. Let $v$ be the vertex which is the
first in $\bar{S}$ according to the topological sort. Let
$\epsilon=\max_{u \in S} \set{w(u,v)}$ ($\epsilon$ may be negative),
and let $e=(u,v)$ be an arc such that $u \in S$ and $w(u,v)=\epsilon$.
If $v=t$, then return a path containing $u$ and $t$. Otherwise, solve
the problem recursively on $(G,S \cup \set{v},w - \epsilon \cdot
\delta)$. Now, let $v_1,\ldots,v_\ell$ be the path returned. If
$v_1=v$, then return the path $u,v_1,\ldots,v_\ell$; otherwise return
$v_1,\ldots,v_\ell$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Acknowledgments}
We thank Guy Even, Eran Mann, Seffi Naor, and especially Ari Freund
for helpful comments and discussions.
%
%This research was partly supported by the N. Haar and R. Zinn Research
%Fund.
%\bibliographystyle{siam}
%\bibliography{62538}
\begin{thebibliography}{10}
\bibitem{AKR95}
{\sc A. Agrawal, P. Klein, and R.~Ravi}, {\em When trees collide: An
approximation algorithm for the generalized {Steiner} problem on networks},
SIAM J. Comput., 24 (1995), pp.~440--456.
\bibitem{BBF99}
{\sc V. Bafna, P. Berman, and T. Fujito}, {\em A
$2$-approximation algorithm for the undirected feedback vertex set problem},
SIAM J. Discrete Math., 12 (1999), pp.~289--297.
\bibitem{BBFNS01}
{\sc A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor, and B.
Shieber}, {\em A unified approach to approximating resource allocation and
scheduling}, J. ACM, 48 (2001), pp.~1069--1090.
\bibitem{Bar00}
{\sc R. Bar-Yehuda}, {\em One for the price of two: A unified approach for
approximating covering problems}, Algorithmica, 27 (2000), pp.~131--144.
\bibitem{BBFR04}
{\sc R. Bar-Yehuda, K. Bendel, A. Freund, and D. Rawitz}, {\em Local
ratio: A unified framework for approximation algorithms}, ACM Comput.
Surveys, 36 (2004), pp.~422--463.
\bibitem{BarEve81}
{\sc R. Bar-Yehuda and S. Even}, {\em A linear time approximation
algorithm for the weighted vertex cover problem}, J. Algorithms, 2 (1981),
pp.~198--203.
\bibitem{BarEve85}
{\sc R. Bar-Yehuda and S. Even}, {\em A local-ratio
theorem for approximating the weighted vertex cover problem}, Ann.
Discrete Math., 25 (1985), pp.~27--46.
\bibitem{BHNSS02}
{\sc R. Bar-Yehuda, M.~M. Halld{\'o}rsson, J. Naor, H. Shachnai, and I. Shapira},
{\em Scheduling split intervals}, in Proceedings of the 13th
Annual {ACM-SIAM} Symposium on Discrete Algorithms, SIAM,
Philadelphia, 2002, pp.~732--741.
\bibitem{BarRaw01}
{\sc R. Bar-Yehuda and D. Rawitz}, {\em Efficient algorithms for bounded
integer programs with two variables per constraint}, Algorithmica, 29 (2001),
pp.~595--609.
\bibitem{BarRaw01b}
{\sc R. Bar-Yehuda and D. Rawitz}, {\em On the equivalence
between the primal-dual schema and the local ratio technique},
in Proceedings of the 4th
International Workshop on Approximation Algorithms for Combinatorial
Optimization Problems, Lecture Notes in Comput. Sci.~2129,
Springer-Verlag, Berlin, 2001, pp.~24--35.
\bibitem{BarRaw04}
{\sc R. Bar-Yehuda and D. Rawitz}, {\em Local ratio with
negative weights}, Oper. Res. Lett., 32 (2004), pp.~540--546.
\bibitem{BarRaw04c}
{\sc R. Bar-Yehuda and D. Rawitz}, {\em Using fractional
primal-dual to schedule split intervals with demands}, in Proceedings
of the 13th Annual European Symposium on Algorithms, Lecture Notes in Comput. Sci.
3669, Springer-Verlag, Berlin, 2005, pp. 714--725.
\bibitem{BecGei96}
{\sc A. Becker and D. Geiger}, {\em Optimization of {P}earl's method of
conditioning and greedy-like approximation algorithms for the vertex feedback
set problem}, Artificial Intelligence, 83 (1996), pp.~167--188.
\bibitem{BerTeo98}
{\sc D. Bertsimas and {C.-P.} Teo}, {\em From valid inequalities to
heuristics: A unified view of primal-dual approximation algorithms in
covering problems}, Oper. Res., 46 (1998), pp.~503--514.
\bibitem{BCFN03}
{\sc R.~Bhatia, J.~Chuzhoy, A.~Freund, and J.~Naor}, {\em Algorithmic aspects
of bandwidth trading}, in Proceedings of the 30th International Colloquium on Automata,
Languages, and Programming, Lecture Notes in Comput. Sci.~2719,
Springer-Verlag, Berlin, 2003, pp.~751--766.
\bibitem{CDZ01}
{\sc M.-C.~Cai, X.~Deng, and W.~Zang}, {\em An approximation algorithm for
feedback vertex sets in tournaments}, SIAM J. Comput., 30 (2001),
pp.~1993--2007.
\bibitem{CGHW98}
{\sc F.~A. Chudak, M.~X. Goemans, D.~S. Hochbaum, and D.~P. Williamson}, {\em A
primal-dual interpretation of recent $2$-approximation algorithms for the
feedback vertex set problem in undirected graphs}, Oper. Res. Lett., 22
(1998), pp.~111--118.
\bibitem{CLR90}
{\sc T.~H. Cormen, C.~E. Leiserson, and R.~L. Rivest}, {\em Introduction to
Algorithms}, MIT Press, Cambridge, MA, 1990.
\bibitem{DFF56}
{\sc G.~B. Dantzig, L.~R. Ford, and D.~R. Fulkerson}, {\em A primal-dual
algorithm for linear programs}, in Linear Inequalities and Related Systems,
H.~W. Kuhn and A.~W. Tucker, eds., Princeton University Press, Princeton, NJ, 1956,
pp.~171--181.
\bibitem{Eve79}
{\sc S. Even}, {\em Graph Algorithms}, Computer Science Press, Woodland Hills, CA, 1979.
\bibitem{EIS76}
{\sc S. Even, A. Itai, and A. Shamir}, {\em On the complexity of
timetable and multicommodity flow problems}, SIAM J. Comput., 5 (1976),
pp.~691--703.
\bibitem{FreRaw03}
{\sc A. Freund and D. Rawitz}, {\em Combinatorial interpretations of dual
fitting and primal fitting}, in Proceedings of the 1st Workshop on Approximation and Online
Algorithms, Lecture Notes in Comput. Sci.~2909,
Springer-Verlag, Berlin, 2003, pp.~137--150.
\bibitem{Fuj98}
{\sc T. Fujito}, {\em A unified approximation algorithm for
node-deletion problems}, Discrete Appl. Math., 86 (1998), pp.~213--231.
\bibitem{GarJoh79}
{\sc M.~R. Garey and D.~S. Johnson}, {\em Computers and Intractability:
A Guide to the Theory of {NP}-Completeness}, W. H. Freeman,
San Francisco, CA, 1979.
\bibitem{GGPSTW94}
{\sc M.~X. Goemans, A.~V. Goldberg, S.~Plotkin, D.~B.~Shmoys, \'E.~Tardos, and D.~P.
Wil\-liam\-son}, {\em Improved approximation algorithms for network design
problems}, in Proceedings of the 5th Annual {ACM-SIAM} Symposium on Discrete Algorithms,
SIAM, Philadelphia, 1994, pp.~223--232.
\bibitem{GoeWil95b}
{\sc M.~X. Goemans and D.~P. Williamson}, {\em A general approximation
technique for constrained forest problems}, SIAM J. Comput., 24 (1995),
pp.~296--317.
\bibitem{GoeWil97}
{\sc M.~X. Goemans and D.~P. Williamson}, {\em The primal-dual method for approximation algorithms and its application to network design
problems}, in Approximation Algorithms for {NP}-Hard Problems,
D.~S. Hochbaum, ed., {PWS} Publishing, Boston, MA, 1997, Chap.~4., pp. 144--191.
\bibitem{GHKO02}
{\sc S. Guha, R. Hassin, S. Khuller, and E. Or}, {\em
Capacitated vertex covering with applications}, in Proceedings of the 13th Annual {ACM-SIAM}
Symposium on Discrete Algorithms, SIAM, Philadelphia, 2002, pp.~858--865.
\bibitem{GusPit92}
{\sc D. Gusfield and L. Pitt}, {\em A bounded approximation for the
minimum cost {$2$-SAT} problem}, Algorithmica, 8 (1992), pp.~103--117.
\bibitem{Hoc97}
{\sc D.~S. Hochbaum, ed.}, {\em Approximation Algorithms for {NP}-Hard
Problems}, {PWS} Publishing, Boston, MA, 1997.
\bibitem{Hoc02}
{\sc D.~S. Hochbaum}, {\em Solving integer
programs over monotone inequalities in three variables: A framework of half
integrality and good approximations}, European J. Oper. Res., 140 (2002),
pp.~291--321.
\bibitem{HMNT93}
{\sc D.~S. Hochbaum, N. Megiddo, J. Naor, and A. Tamir}, {\em
Tight bounds and $2$-approximation algorithms for integer programs with two
variables per inequality}, Math. Program., 62 (1993), pp.~69--83.
\bibitem{JMMSV03}
{\sc K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. Vazirani},
{\em Greedy facility location algorithms analyzed using
dual-fitting with factor-revealing {LP}}, J. ACM, 50 (2003), pp.~795--824.
\bibitem{JaiVaz01}
{\sc K. Jain and V.~V. Vazirani}, {\em Approximation algorithms for
metric facility location and k-median problems using the primal-dual schema
and {Lagrangian} relaxation}, J. ACM, 48 (2001), pp.~274--296.
\bibitem{Kar91}
{\sc H. Karloff}, {\em Linear Programming}, Progr. Theoret. Comput. Sci.,
{Birkh\"{a}user} Boston, Boston, MA, 1991.
\bibitem{PapSte82}
{\sc C.~H. Papadimitriou and K. Steiglitz}, {\em Combinatorial
Optimization: Algorithms and Complexity}, 5th~ed., Prentice-Hall, Englewood Cliffs, NJ, 1982.
\bibitem{RK93}
{\sc R.~Ravi and P.~Klein}, {\em When cycles collapse: A general approximation
technique for constrained two-connectivity problems}, in Proceedings of the 3rd MPS Conference
on Integer Programming and Combinatorial Optimization, CIACO, Louvain-la-Neuve,
Belgium, 1993, pp.~39--56.
\bibitem{Vaz01}
{\sc V.~V. Vazirani}, {\em Approximation Algorithms}, 2nd~ed., Springer-Verlag,
Berlin, 2001.
\bibitem{Wil02}
{\sc D.~P. Williamson}, {\em The primal dual method for approximation
algorithms}, Math. Program., 91 (2002), pp.~447--478.
\bibitem{WGMV95}
{\sc D.~P. Williamson, M.~X. Goemans, M. Mihail, and V.~V.
Vazirani}, {\em A primal-dual approximation algorithm for generalized
{S}teiner network problems}, Combinatorica, 15 (1995), pp.~435--454.
\end{thebibliography}
\end{document}