%\documentstyle[10pt,twoside]{article} %\documentstyle[twoside]{article} \documentclass[twoside]{article} \setlength{\oddsidemargin}{0 in} \setlength{\evensidemargin}{0 in} \setlength{\topmargin}{-0.6 in} \setlength{\textwidth}{6.7 in} \setlength{\textheight}{8.5 in} \setlength{\headsep}{0.75 in} \setlength{\parindent}{0 in} \setlength{\parskip}{0.1 in} \usepackage{amsmath,amssymb,enumerate,algorithms,ifthen} \usepackage{graphicx,picins} % The following commands sets up the lecnum (lecture number) % counter and make various numbering schemes work relative % to the lecture number. % \newcounter{lecnum} \renewcommand{\thepage}{\thelecnum-\arabic{page}} \renewcommand{\thesection}{\thelecnum.\arabic{section}} \renewcommand{\theequation}{\thelecnum.\arabic{equation}} \renewcommand{\thefigure}{\thelecnum.\arabic{figure}} \renewcommand{\thetable}{\thelecnum.\arabic{table}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{claim}{Claim} \newtheorem{proposition}{Proposition} \newtheorem{prob}{Problem} \newtheorem{corollary}{Corollary} \newtheorem{question}{Question} \newtheorem{conjecture}{Conjecture} \newtheorem{example}{Example} \newtheorem{definition}{Definition} \newtheorem{remarka}{Remark} \def\P{\mathop{\rm P}\nolimits} \def\NP{\mathop{\rm NP}\nolimits} \def\DTIME{\mathop{\rm DTIME}\nolimits} \def\BPTIME{\mathop{\rm BPTIME}\nolimits} \def\ZPTIME{\mathop{\rm ZPTIME}\nolimits} \def\polylog{\mathop{\rm polylog}\nolimits} \newenvironment{remark}{\begin{remarka}\rm}{\end{remarka}} \newenvironment{proof}{{\bf Proof.}}{\hfill\rule{2mm}{2mm}} \newenvironment{pproof}[1]{\noindent{\textbf{Proof of #1.}}}{\hfill\rule{2mm}{2mm}} \newcommand{\calI}{{\cal I}} \newcommand{\calT}{{\cal T}} \newcommand{\calP}{{\cal P}} \newcommand{\opt}{\mbox{\sc opt}} \newcommand{\OPT}{\mbox{\sc OPT}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ZZ}{\mathbb{Z}} % % The following macro is used to generate the header. % \newcommand{\lecture}[5]{ \pagestyle{myheadings} \thispagestyle{plain} \newpage \setcounter{lecnum}{#1} \setcounter{page}{1} \noindent \begin{center} \framebox{ \vbox{\vspace{2mm} \hbox to 6.28in { {\bf CMPUT 675: Approximation Algorithms \hfill Fall 2015} } \vspace{4mm} \hbox to 6.28in { {\Large \hfill Lecture #1 (#2): #3 \hfill} } \vspace{2mm} \hbox to 6.28in { {\it Lecturer: #4 \hfill Scribe: #5} } \vspace{2mm}} } \end{center} \markboth{Lecture #1: #3}{Lecture #1: #3} \vspace*{4mm} } % % Convention for citations is authors' initials followed by the year. % For example, to cite a paper by Leighton and Maggs you would type % \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}. % (To avoid bibliography problems, for now we redefine the \cite command.) % \renewcommand{\cite}[1]{[#1]} \input{epsf} %Use this command for a figure; it puts a figure in wherever you want it. %usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME} \newcommand{\fig}[4]{ \vspace{0.2 in} \setlength{\epsfxsize}{#2} \centerline{\epsfbox{#4}} \begin{center} Figure \thelecnum.#1:~#3 \end{center} } % Use these for theorems, lemmas, proofs, etc. % Some useful equation alignment commands, borrowed from TeX \makeatletter \def\eqalign#1{\,\vcenter{\openup\jot\m@th \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil \crcr#1\crcr}}\,} \def\eqalignno#1{\displ@y \tabskip\@centering \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip &$\displaystyle{{}##}$\hfil\tabskip\@centering &\llap{$##$}\tabskip\z@skip\crcr #1\crcr}} \def\leqalignno#1{\displ@y \tabskip\@centering \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip &$\displaystyle{{}##}$\hfil\tabskip\@centering &\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr #1\crcr}} \makeatother % **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE: \begin{document} %FILL IN THE RIGHT INFO. %\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**} \lecture{1}{Sept 1 and 3, 2015}{Introduction}{Mohammad R. Salavatipour}{Mohammad R. Salavatipour} % **** YOUR NOTES GO HERE: % Some general latex examples and examples making use of the % macros follow. %**** IN GENERAL, BE BRIEF. LONG SCRIBE NOTES, NO MATTER HOW WELL WRITTEN, %**** ARE NEVER READ BY ANYBODY. %This lecture's notes illustrate some uses of %various \LaTeX\ macros. %Take a look at this and imitate. % %\section{Some theorems and stuff} % Don't be this informal in your notes! % %We now delve right into the proof. % %\begin{lemma} %This is the first lemma of the lecture. %\end{lemma} % %\begin{proof} %The proof is by induction on \ldots. %For fun, we throw in a figure. %%%%NOTE USAGE ! %\fig{1}{1in}{A Fun Figure}{funfig.eps} % %This is the end of the proof, which is marked with a little box. %\end{proof} % %\subsection{A few items of note} % %Here is an itemized list: %\begin{itemize} %\item this is the first item; %\item this is the second item. %\end{itemize} % %Here is an enumerated list: %\begin{enumerate} %\item this is the first item; %\item this is the second item. %\end{enumerate} % %Here is an exercise: % %{\bf Exercise:} Show that ${\rm P}\ne{\rm NP}$. % %Here is how to define things in the proper mathematical style. %Let $f_k$ be the $AND-OR$ function, defined by % %\[ f_k(x_1, x_2, \ldots, x_{2^k}) = \left\{ \begin{array}{ll} % % x_1 & \mbox{if $k = 0$;} \\ % % AND(f_{k-1}(x_1, \ldots, x_{2^{k-1}}), % f_{k-1}(x_{2^{k-1} + 1}, \ldots, x_{2^k})) % & \mbox{if $k$ is even;} \\ % % OR(f_{k-1}(x_1, \ldots, x_{2^{k-1}}), % f_{k-1}(x_{2^{k-1} + 1}, \ldots, x_{2^k})) % & \mbox{otherwise.} % \end{array} % \right. \] % %\begin{theorem} %This is the first theorem. %\end{theorem} % %\begin{proof} %This is the proof of the first theorem. We show how to write pseudo-code now. %%*** USE PSEUDO-CODE ONLY IF IT IS CLEARER THAN AN ENGLISH DESCRIPTION % %Consider a comparison between $x$ and~$y$: %\begin{tabbing} %\hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \=\kill %\>{\bf if} $x$ or $y$ or both are in $S$ {\bf then } \\ %\>\> answer accordingly \\ %\>{\bf else} \\ %\>\> Make the element with the larger score (say $x$) win the comparison \\ %\>\> {\bf if} $F(x) + F(y) < \frac{n}{t-1}$ {\bf then} \\% %\>\>\> $F(x) \leftarrow F(x) + F(y)$ \\ %\>\>\> $F(y) \leftarrow 0$ \\ %\>\> {\bf else} \\ %\>\>\> $S \leftarrow S \cup \{ x \} $ \\ %\>\>\> $r \leftarrow r+1$ \\ %\>\> {\bf endif} \\ %\>{\bf endif} %\end{tabbing} % %This concludes the proof. %\end{proof} % % %\section{Next topic} % %Here is a citation, just for fun \cite{CW87}. % % **** THIS ENDS THE EXAMPLES. DON'T DELETE THE FOLLOWING LINE: \section{Introduction} In this course we will be studying how to design approximation algorithms for NP-hard optimization problems through a series of problems. Some of our objectives are: to learn some techniques for design and analysis of such algorithms; have a better understanding of problems that are NP-hard and do a (partial) classification based on the level of difficulty of these problems. This is done by study of hardness of approximation for these problems. Recall that $\P$ is the class of problems solvable in polynomial time and $\NP$ (informally) are those (decision) problems whose solutions can be verified by a polynomial time algorithm. We will be studying NP-hard optimization problems. For these problems, we would like to: \begin{enumerate} \item find the optimal solution, \label{first} \item find the solution fast, often in polynomial time \label{second} \item find solutions for any instance \label{third} \end{enumerate} Unfortunately, with the assumption of $\P \ne \NP$, we cannot have all the above three at the same time. Therefore, we need to relax at least one of them. If we: \begin{enumerate} \item relax (\ref{third}), then we are into study of special cases of the problem. \item relax (\ref{second}), we will be in the field of integer programming and the techniques there such as branch-and-bound, etc. \item relax (\ref{first}), we are into study of heuristics and approximation algorithms. \end{enumerate} We are going to focus on the (\ref{third}) in this course, and in particular, on the field of approximation algorithms. We are interested in: \begin{itemize} \item finding solutions that are within a guaranteed factor of the optimal solutions, and \item We want to find this solution fast (i.e. polynomial time). \end{itemize} Why is it important to study approximation algorithms? \begin{itemize} \item We need to solve optimization problems (they appear everywhere!). Saying that because they are NP-hard we don't know of any efficient way of solving them is not enough. If you cannot find the optimal solution, try your best! \item We can prove how good the solution is (this is sometimes critical in applications). \item We can have an understanding of how hard the problem is, and this in turn can help to design better algorithms. \item Tools and algorithmic ideas can often give practical and good heuristics and have applications to other areas. \item Solving very challenging problems using beatiful (sometimes neat and sometimes sophisticated) ideas is fun! \end{itemize} Throughout the course, we often ignore optimizing the running time as long as it is polynomial. We also ignore implementation and engineering aspects or how close the model we study is to the application it came from. Instead we will be focusing on designing algorithms with best possible performance ratio. Let's start with an example. Consider the Vertex-Cover problem. {\bf Vertex-Cover:} \begin{itemize} \item{Input} \begin{itemize} \item $G:$ an undirected graph $G=(V,E)$ \item $c:$ a cost function on vertices, $c: V \rightarrow \QQ^{+}$ \end{itemize} \item{Goal:} find a minimum cost vertex cover, i.e., a set $V^{\prime} \subseteq V$ such that every edge has at least one endpoint incident at $V^{\prime}$. \end{itemize} The special case, in which all vertices are of unit cost, is called the {\it cardinality vertex cover problem}. Let's consider the cardinality VC for now. Perhaps the most natural greedy algorithm for this problem is the following algorithm: \begin{figure}[h] \fbox{ \parbox{\textwidth}{ {\bf Algorithm VC1 } \begin{itemize} \item $S \leftarrow \emptyset$ \item {\bf while} $ E \ne \emptyset$ {\bf do} \begin{itemize} \item $ \textrm{let} \ v \ \textrm{be a vertex of maximum degree in} \ G$ \item $ S \leftarrow S \ \cup \{v\}$ \item $ \textrm{remove} \ v \ \textrm{and all its edges from} \ G$ \end{itemize} \item $\textrm{return} \ S$ \end{itemize} }} \end{figure} We will see that the approximation ratio for Algorithm VC1 is $O(\log \Delta)$, where $\Delta$ is the maximum degree in graph $G$. \section{NP Optimization problems} An $\NP$ optimization problem, $\Pi$, is a minimization (maximization) problem which consists of the following items: \begin{description} \item{Valid instances:} each valid instance $I$ is recognizable in polynomial time. (note: 'Polynomial time' means polynomial time in terms of the size of the input.) The set of all valid instances is denoted by $D_{\Pi}$. The size of an instance $I \in D_{\Pi} $, denoted by $|I|$, is the number of bits required to represent $I$ in binary. \item{Feasible solutions:} Each $I \in D_{\Pi} $ has a set $S_{\Pi}(I)$ of feasible solutions and for each solution $s \in S_{\Pi}(I)$, $|s|$ is polynomial (in $|I|$). \item{Objective function:} A polynomial time computable function $f(s, I)$ that assigns a non-negative rational value to each feasible solution $s$ for $I$. We often have to find a solution $s$ such that this objective value is minimized (maximized). This solution is called optimal solution for $I$, denoted by $OPT(I)$. \end{description} Examples: \begin{itemize} \item{Vertex Cover:} In this case we have: \begin{description} \item{valid instances :} set of graphs with weighted vertices. \item{feasible solutions :} all the vertex covers of the given graph. \item{objective functions :} minimizing the total weight of a vertex cover. \end{description} \item{Minimum Spanning Tree (MST) problem:} Given a connected graph $G(V,E)$, with each edge $(u,v)\in E$ assigned a weight $w(u,v)$, find an acyclic subset $T \subseteq E$ that connects all the vertices and its total weight is minimized. Since $T$ is acyclic and connects all of the vertices, it is a tree. \begin{description} \item{valid instances :} a graph with weighted edges. \item{feasible solutions :} all the spanning trees of the given weighted graph. \item{objective functions :} minimizing the total weight of a spanning tree. \end{description} \end{itemize} \section{Approximation algorithms} An {\it $\alpha$-factor approximation algorithm} (or simply an $\alpha$-approximation) is a polynomial time algorithm whose solution is always within $\alpha$ factor of optimal solution. \begin{definition}\label{def:factor} For a minimization problem $\Pi$, algorithm $A$ has approximation factor $\alpha$ if it runs in polynomial time and for any instance $I \in D_{\Pi}$ it produces a solution $s \in S_{\Pi}(I)$ such that $f(s,I) \leq \alpha(|I|) \cdot OPT(I)$. $\alpha$ can be a constant or a function of the size of the instance. \end{definition} We use $A(I)$ to denote the value of the solution returned by algorithm $A$ for instance $I$; therefore, from Definition~\ref{def:factor}: $A(I) \leq \alpha(|I|) \cdot OPT(I)$. Similarly, for a maximization problem, we have \begin{itemize} \item $OPT(I) \le \alpha(|I|) \cdot A(I)$, if $\alpha > 1$; \item or $OPT(I) \le \frac{A(I)}{\alpha(|I|)}$, if $\alpha < 1$. \end{itemize} \begin{definition} Algorithm $A$ has asymptotic $\alpha$-approximation ratio if the ratio $\lim_{|I| \rightarrow \infty}\frac{A(I)}{OPT(I)} \le \alpha $ \end{definition} Intuitively, for large enough instances, the approximation ratio of the algorithm is almost $\alpha$ (although for small instances it might be larger). Just as there are randomized algorithms that compute exact solutions, there are randomized algorithms that compute approximate solutions. \begin{definition} An algorithm $A$ is a randomized factor $\alpha$-approximation for problem $\Pi$ if for any instance $I \in D_{\Pi}$, $A$ produces a feasible solution $s$ such that $Pr[f(s,I) \le \alpha(|I|) \cdot OPT(I)] \ge \frac{1}{2}$. \end{definition} This probability can be increased to ($1-\frac{1}{2^x}$) by repeating the same algorithm $A$ for $x$ times. \begin{definition} A (uniform) PTAS (Polynomial Time Approximation Scheme) for an optimization problem is an approximation algorithm $A$ that takes as input not only an instance of the problem, but also a value $\epsilon > 0 $, and runs in time polynomial in $n$ and returns a solution $s$ that satisfies: $f(s,I)\leq (1+\epsilon)\cdot OPT(I)$, i.e. it is a $(1+\epsilon)$-approximation algorithm. \end{definition} In case of non-uniform PTAS we have a class of algorithms $\{A_\epsilon\}$, one for every possible value of $\epsilon$. A running time $O(n^{\frac{1}{\epsilon}})$ is still polynomial for any fixed $\epsilon$, but computations with $\epsilon$ values very close to $1$ may turn out to be practically not feasible. This leads to the definition of $FPTAS$, a more restricted version of $PTAS$ and much faster than $PTAS$. \begin{definition} FPTAS(Fully Polynomial-Time Approximation Scheme) For a minimization problem $\Pi$, a FPTAS algorithm $A$ takes an instance $I$ and error bound $\epsilon > 0$, and returns a solution $s$ such that $f(s,I) \le (1+\epsilon) \cdot OPT(I)$. $A$ runs in polynomial time in terms of both $|I|$ and $\epsilon$ (i.e. $\epsilon$ can not appear in exponent). \end{definition} Example: $O(\frac{n^{2}}{\epsilon^{2}})$ vs. $O(n^{\frac{1}{\epsilon}})$ Some problems like Knapsack, Euclidean TSP, and some scheduling problems belong to class PTAS. Problems like MAX-SAT, Vertex-Cover, are much harder and don't admit a PTAS. These problems belong to a class called APX-hard, which is the class of problems that have a constant approximation but don't have a PTAS. \section{A 2-Approximation for Cardinality Vertex Cover} Recall the definition of the cardinality vertex cover problem. \begin{itemize} \item Input: An undirected graph $G = (V,E)$. \item Goal: Find a minimum cardinality set of vertices $S \subseteq V$ such that every edge in $E$ has at least one endpoint in $S$. \end{itemize} \begin{definition} A {\em matching} in a graph $G = (V,E)$ is a subset of edges $M \subseteq E$ such that no two edges in $M$ share a common endpoint. A matching $M$ is called {\em maximal} if it is not strictly contained in any other matching ({\em i.e.} no edges in $E\setminus M$ can be added to $M$). \end{definition} Our second vertex cover algorithm simply finds any maximal matching $M$. The cover is defined as all endpoints of edges in $M$. \noindent \fbox{ \parbox{\textwidth}{ {\bf Algorithm VC2} \begin{tabbing} \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \=\kill \>$S \leftarrow \emptyset$ \\ \>{\bf while} $E \neq \emptyset$ {\bf do} \\ \>\>let $uv$ be any edge in $E$ \\ \>\>$S \leftarrow S \cup \{u,v\}$ \\ \>\>delete $u, v$, and all their incident edges from $G$ \\ \>{\bf return} $S$ \\ \end{tabbing} }} \begin{lemma} The set $S$ returned by $VC2$ is a vertex cover. \end{lemma} \begin{proof} Consider any edge $e$ deleted in an iteration of the loop. If $e$ was selected as the edge in the first line of the loop, then both of its endpoints were added to $S$. Otherwise, $e$ must share an endpoint with the edge selected in the first line of the loop so one of its endpoints is added to $S$. Since all edges are eventually deleted in some iteration, the final set $S$ is a vertex cover. \end{proof} \begin{lemma}\label{vc-dual} Let $M$ be any matching and $S$ be any vertex cover. Then, $|M| \leq |S|$. \end{lemma} \begin{proof} Each $e \in M$ must have at least one of its endpoints covered by $S$. Since $M$ is a matching then no two edges in $e$ share an endpoint. Therefore, each $e \in M$ is covered by a vertex that covers no other $e' \in M$ so $|M| \leq |S|$. \end{proof} \begin{lemma} $VC2$ is a 2-approximation. \end{lemma} \begin{proof} Let $M$ be the set of all edges selected in the first line of the loop. Then $M$ is a matching since any edge sharing an endpoint with some $e \in M$ was deleted in the third line of the loop. Since $S$ consists exactly of the endpoints of edges in $M$ then $|S| = 2|M|$. Say $OPT$ is the size of the smallest vertex cover. Then, by lemma \ref{vc-dual}, $|S| = 2|M| \leq 2\cdot OPT$. \end{proof} The analysis of the approximation ratio of $VC2$ is tight. Consider the complete bipartite graph $K_{n,n}$ with $n$ vertices on each side of the bipartition. All $2n$ vertices will be selected by $VC2$ whereas it is sufficient to only select all $n$ vertices from one of the bipartitions. %The best known algorithm for vertex cover has ratio $2 - (1-o(1))\frac{2\ln\ln\Delta}{\ln\Delta}$ The best known algorithm for vertex cover has ratio $2 - \Theta(\log^{-1/2} |V|)$ (Karakostas, 04). Currently, the best lower bound that assumes $\P \neq \NP$ shows that vertex cover cannot be approximated within a factor of $10 \sqrt 5 - 21 > 1.3606$ (Dinur and Safra, 02). A tighter lower-bound can be obtained under the {\em unique games conjecture}; a much stronger assumption than $\P \neq \NP$. This lower-bound states that vertex cover cannot be approximated within $2 - \epsilon$ for any constant $\epsilon > 0$ (Khot and Regev, 03). % If you need to add references, use the following format: %\section*{References} % %\begin{itemize} %\item[CW87] {\sc D.~Coppersmith} and {\sc S.~Winograd}, %Matrix multiplication via arithmetic progressions, %{\it Proceedings of the 19th ACM Symposium on Theory of Computing}, %1987, pp.~1--6. % %\item[S69] {\sc V.~Strassen}, Gaussian Elimination Is Not Optimal, %{\it Numerische Mathematik\/~\bf13}, 1969, pp.~354--356. % %\item[P84] {\sc V.~Pan}, {\it How To Multiply Matrices Faster}, %Springer-Verlag, Lecture Notes in Computer Science Vol.~179, 1984. % %\end{itemize} \section{Steiner Tree} Steiner tree problem is a very well studied problem that generalizes the Minimum Spanning Tree problem. This problem (and its generalizations that we see in future) has a wide range of applications in fields like VLSI design, computer networks, and computational biology. {\bf Steiner tree problem:} Given an undirected graph $G = (V,E)$ with cost function $c : E\rightarrow \QQ^+$, and a subset $T \subseteq V$ called terminals, the goal is to find a minimum cost tree spanning all vertices in $T$ . The vertices in $S = V - T$ are called Steiner nodes. One of the special cases of Steiner tree is Spanning tree in which $T = V$ . As we all know, minimum Spanning tree problem can be solved in polynomial time. But the Minimum Steiner problem is NP-hard. Before we study this problem we discuss a notion that we will use later on in the course very frequently. We say a cost function $c$ satisfies metric property (or is a metric) if: \begin{itemize} \item $c(u, u) = 0$ for all points $u$, \item $c(u, v) = c(v, u)$ for all pairs of points $u, v$, \item $c(u, v) \leq c(u,w) + c(w, v)$ for all $u, v,w$ (triangle inequality) \end{itemize} By this defintion, when we say that $G = (V,E)$ has metric cost function it means that $c(u, v)$ is defined for every pair of nodes (so $G$ is a complete graph) and in particular it satisfies the triangle inequality condition. We will consider the restriction of the problem to the metric case. We show that this restricted version of the problem is in fact as hard as the general version: \begin{theorem} There is an approximation factor preserving reduction from the Steiner tree problem to the metric Steiner tree problem. \end{theorem} \begin{proof} Given $G(V,E)$ as an instance for the general case, construct the complete graph $G'$ on $V$ by assigning $c_{G'}(uv)$ (cost of $uv$ in $G'$) to be the cost of the shortest $uv$-path in $G$. The set of terminals in $G'$ is the same as in $G$. Trivially this is a metric instance (follows directly from the definition and property of shortest paths). \begin{claim} The cost of optimal solution to $G'$ is less than or equal to the cost of optimal solution of $G$. \end{claim} \begin{proof} This is because for any edge $uv$ in $G$, $c_{G'}(uv) \leq c_G(uv)$. \end{proof} \begin{claim} The cost of optimal solution to $G$ is less than or equal to the cost of optimal solution to $G'$. \end{claim} \begin{proof} Take any optimal Steiner tree $H'$ for $G'$ and replace each edge $vw$ in $H'$ by the shortest path between $v$ and $w$ in $G$ to obtain a subgraph of $G$. Remove the extra edges (if needed) to remove all cycles of this subgraph; hence what is left is a Steiner tree in $G$, call it $H$. Clearly, the cost does not increase during this process. Therefore: $cost(H ) \leq cost(H')$. \end{proof} The proof of theorem follows from the above two claims. \end{proof} By this theorem, it is enough to consider only metric instances of the Steiner tree problem. Graph $G'$ built above is called the metric completion of $G$. Now we present a simple 2-approximation for metric Steiner tree. \noindent \fbox{ \parbox{\textwidth}{ {\bf Algorithm Steiner-Tree(G, T )} \begin{tabbing} \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \=\kill \> Find a minimum spanning tree in subgraph of $G$ induced by $T$ , $G[T]$.\\ \> Return this as the solution. \end{tabbing} }} \begin{lemma} The above algorithm is a factor $2-\frac{2}{|T|}$-approximation algorithm for Steiner tree. \end{lemma} \begin{proof} It is simple to see that the algorithm finds a feasible solution in polynomial time. To prove its factor, let $T_{opt}$ be an optimal Steiner tree. Double every edge of $T_{opt}$ and find an Eulerian walk on this graph. Traverse Eulerian walk and shortcut over Steiner Points and visited terminal vertices to reach a simple cycle $C$ on terminals. Then, delete the heaviest edge from the cycle to reach simple path $P$ on terminals. Let $OPT$ be the cost of $T_{opt}$ and $OPT_{mst}$ be the cost of minimum spanning tree in $G[T ]$. Since $G$ satisfies triangular inequality, $c(C)$ (i.e. the cost of $C$) is not more than the cost of initial Eulerian walk and that is $2OPT$ . Because the weight of heaviest edge in this cycle is at least $c(C)/|C|=c(C)/|T|$ and $P$ is a spanning tree in $G{T}$ we have: $$OPT_{mst} \leq c(P)\leq \left(1-\frac{1}{|T|}\right) c(C)\leq \left(2-\frac{2}{|T|}\right) OPT,$$ which completes the proof. \end{proof} The best known approximation algorithm for Steiner tree uses iterative rounding (an LP solution) and has ratio $ln(4) + \epsilon < 1.39$. \section{Traveling Salesman Problem (TSP)} This is a very well-known NP-hard problem. There are at least three books written on this problem. \begin{definition} {\bf Traveling Salesman Problem (TSP):} Given a complete graph $G(V,E)$ on $n$ vertices with edge cost $c:E\longrightarrow \QQ^{+}$, find a minimum cost cycle visiting every vertex exactly once, i.e. a minimum cost Hamiltonian cycle. \end{definition} Finding a Hamiltonian cycle in a graph is NP-hard. Using this fact, we show that TSP cannot have an approximation algorithm in the general case. \begin{theorem} For any polynomially computable function $f(\cdot)$, TSP does not have an $f(n)$-approximation algorithm unless P=NP. \end{theorem} \begin{proof} Let $G$ be the instance of Hamiltonian cycle problem and construct $G'$ on the same vertex set in the following way: \begin{itemize} \item If $e \in G$, then the cost of $e$ in $G'$ is 1. \item If $e \not\in G$, the cost of $e$ in $G'$ is $f(n)\cdot (n+1)$, where $n$ is the number of vertices in G. \end{itemize} If $G$ has a Hamiltonian cycle then the TSP tour in $G'$ has cost $n$ and an $f(n)$-approximation returns a solution of cost at most $f(n)\cdot n)$. If $G$ does not have a Hamiltonian cycle then every TSP tour in $G'$ must use at least one of those heavy edges and therefore has cost larger than $f(n)\cdot (n+1)$. Thus, if we have an algorithm $A$ for TSP with factor $f(n)$, we can decide whether $G$ has a Hamiltonian cycle, which is NP-hard. \end{proof} \subsection{Approximation of metric TSP} So let's focus on the metric instances of TSP. A distance function $d:X\times X\rightarrow \RR^+$ defined over $X$ is a metric if: \begin{itemize} \item $d(u,u)=0$ for all $u\in X$. \item $d(u,v)=d(v,u)$ for all $u,v\in X$ \item $d(u,v)\leq d(u,w)+d(w,v)$ for all $u,v,w\in X$. \end{itemize} The third condition is called triangle inequality. Since TSP is not approximable in general we focus on weighted graphs where the cost function is a metric. This means, the input graph is a complete graph and the edge weights satisfy triangle inequality. For example, one can take the metric completion of the input graph which is the graph whose edge weights are the shortest path distances of the original graph. It is easy to see that the shortest path distances define a metric. From now on, when we talk about TSP we will be assuming metric graphs. This assumption implies a complete graph obeying the triangle inequality. The first algorithm we present is a simple 2-approximation that uses minimum spanning tree. Note that if $T$ is a MST then $c(T) \leq OPT_{TSP}$ since deleting any edge from a TSP tour results in a tree. \noindent \fbox{\parbox{\textwidth}{ {\bf Algorithm TSP1} \begin{tabbing} \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \=\kill \> 1) Find a MST $T$ in the input graph\\ \> 2) Duplicate all edges and call this new graph $T'$. (Note: $Cost(T') = 2Cost(T)$ )\\ \> 3) Find an Eulerian walk (a path that uses all edges in a graph). Let's call this walk $W$. \\ \> 4) Find a path $P$ by following $W$, but shortcutting to the next unvisited vertex along $W$.\\ \end{tabbing} }} Note: $Cost(T) \leq OPT_{TSP}$ and $Cost(P) \leq Cost(T')$ by the metric property. So we can see that we have a 2-approximation of TSP. We next see how we can improve the approximation ratio of the previous algorithm. The factor 2 loss in the approximation ratio came from doubling the edges of the MST found. The reason we doubled the edges was to find an Eulerian graph (i.e. a graph in which all degrees are even). The improvement comes by adding fewer edges to $T$. Let $O$ be the set of odd degree nodes of $T$. Note that $|O|$ is even. We find a minimum cost matching over $O$, call it $M$ and add this to $T$. It is easy to see that $T+M$ is now an Eulerian graph as all the degrees are even. We will argue that the cost of the matching $M$ added will be at most $OPT_{TSP}/2$ and this will imply a $3/2$-approximation. \noindent \fbox{ \parbox{\textwidth}{ {\bf Algorithm TSP2} \begin{tabbing} \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \=\kill \> 1) Find $T$ a MST on the graph; let $O$ be the set of odd degree nodes of $T$.\\ \> 2) Find a minimum cost matching $M$ over $O$.\\ \> 3) Create a new graph $M+T$.\\ \> 4) Repeat steps 3 $\&$ 4 from TSP1 on $M+T$. \end{tabbing} }} Therefore, we only need to show that $cost(M) \leq OPT_{TSP}/2$, since the cost of Euler tour found in Step 3 is exactly $cost(T)+cost(M)$. The following lemma completes the proof of this algorithm. \begin{lemma} Let $V'\subseteq V$ s.t $|V'|$ is even and let $M$ be a minimum cost perfect matching on $V'$. Then the $cost(M) \leq OPT_{TSP}/2$. \end{lemma} \begin{proof} Consider any optimal TSP tour $\tau$ of $G$ and let $\tau'$ be the tour obtained from $\tau$ by shortcutting on the vertices of $V-V'$, i.e. skip the vertices of $V-V'$. So $\tau'$ is a tour on $V'$ only and $cost(\tau')\leq cost(\tau)$ because we have a metric instance. Now, since $|V'|$ is even, $\tau'$ can be decomposed to two perfect matchings by choosing the even edges or the odd edges on the tour. Since the cost of a minimum perfect matching on $V'$ is smaller that each of these: $cost(M) \leq \frac{1}{2} cost(\tau') \leq OPT_{TSP}/2$. \end{proof} From the lemma, we can obtain the guarantee ratio for the algorithm to be $\frac{3}{2}$. This algorithm, called Christofides, is the best known approximation algorithm for TSP for the past 36 years. {\bf Major open problem:} Obtain a better approximation algorithm for metric TSP or prove that there is no such algorithm, under some reasonable complexity assumption. \section{Set Cover Problem} Now we turn our attention to the Set Cover problem, which is (perhaps) the most central problem in the study of approximation algorithms. There are different algorithms for this problem. In this course we will see at least 4 different approximation algorithms for this using different methods. {\bf Set Cover:} \begin{itemize} \item Input: \begin{itemize} \item A set of $n$ elements $U = \{e_1, \dots, e_n\}$, called the Universe. \item A set $S = \{S_1, \dots, S_m\}$ of $m$ subsets of $U$ such that each $e \in U$ is in some $S_i \in S$ \item A cost function $c : S \rightarrow \mathbb{Q}^+$ \end{itemize} \item Goal: Find a minimum cost subset $S'$ of $S$ such that each $e \in U$ is in some $S_i \in S'$. \end{itemize} Note that vertex cover is a special case of set cover where $U$ is the set of all edges and each vertex $v$ is a subset in $S$ which contains all edges incident to $v$. In this case, each element is in exactly two subsets in $S$. We present a greedy approximation algorithm for Set Cover. This is probably the most natural greedy algorithm for this problem. The idea is, at each iteration pick a set where the ratio of the cost of the set divided by the number of new elements it covers is minimized. This general idea of ``covering'' elements iteratively by finding good partial solutions has been used in many other problems. The analysis of set-cover (we present here) can typically be extended to those other covering algorithms that behave similarly. \begin{definition} Given a subset $C$ of $U$, define the cost effectiveness of set $S_i \in S$ as $\frac{c(S_i)}{|S_i - C|}$. If $S_i \subseteq C$ then say the cost effectiveness is $+\infty$. \end{definition} \noindent {\bf Algorithm SC1} \begin{tabbing} \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \=\kill \>$C \leftarrow \emptyset$ \\ \>$S' \leftarrow \emptyset$ \\ \>{\bf while} $C \neq U$ {\bf do} \\ \>\>select $S_i \in S$ with minimum cost effectiveness $\alpha = \frac{c(S_i)}{|S_i - C|}$ with respect to $C$ \\ \>\>for each $e \in S_i$, define $price(e)$ as $\alpha$ \\ \>\>$S' \leftarrow S' \cup \{S_i\}$ \\ \>\>$C \leftarrow C \cup S_i$ \\ \>{\bf return} $S'$ \\ \end{tabbing} Obviously, all elements are eventually covered by $S'$ since the algorithm terminates only when $C = U$. Note that the final cost of set $S'$ is $\sum_{e \in U} price(e)$ since, for each $S_i \in S'$, the cost of $S_i$ is distributed among all elements in $S_i$ that were covered for the first time when $S_i$ was picked. \begin{lemma} Algorithm $SC1$ is an $\ln n$-approximation algorithm; more precisely it has ratio at most $H_n$, where $H_n$ is the $n$'th harmonic number. \end{lemma} \begin{proof} Let $T_{OPT} \subseteq S$ be a set cover with minimum cost $OPT$. Order the elements of $U$ by the time they were covered by algorithm SC1 (breaking ties arbitrarily) as $e_1, e_2, \dots, e_n$. Consider the time just before $e_k$ is covered. The remaining at least $n-k+1$ elements can be covered at a price of no more than $OPT$ by adding the currently unselected sets of $T_{OPT}$ to $S'$. In other words, each element can be covered at a price of no more than $\frac{OPT}{n-k+1}$ on average. We claim that there must be a set with cost effectiveness at most $\frac{OPT}{n-k+1}$. If this were not true, then the cost of covering the remaining uncovered elements would be strictly greater than $(n-k+1)\cdot\frac{OPT}{n-k+1} = OPT$ which contradicts the fact that the remaining elements can be covered at a cost of at most $OPT$ by selecting $T_{OPT}$. Thus, $price(e_k) \leq \frac{OPT}{n-k+1}$ which yields \[ \displaystyle{\sum_{k=1}^n}~price(e) \leq \displaystyle{\sum_{k=1}^n}~\frac{OPT}{n-k+1} = OPT \cdot \displaystyle{\sum_{k=1}^n}~\frac{1}{k} = OPT \cdot H_n \] where $H_n$ is the $n'th$ harmonic number. By comparison with $\int \frac{dx}{x}$ we see that $\ln n \leq H_n \leq \ln n + 1$. Therefore $SC1$ is an $O(\log n)$ approximation algorithm. \end{proof} Through similar analysis, we can show that $SC1$ is an $O(\log k)$-approximation where $k = \max |S_i|$. Note that this proves the ratio of $O(\log \Delta)$ for the greedy vertex cover algorithm where $\Delta$ is the size of maximum degree of nodes. The analysis of $SC1$ is also tight. For any $\epsilon > 0$ being a small constant, consider the following instance of set cover (illustrated in Figure \ref{sc1-tight}): \begin{itemize} \item $U = \{e_1, \dots, e_n\}$ \item $S = \{S_0, S_1, \dots, S_n\}$ \item $c(S_0) = 1 + \epsilon$ and $c(S_i) = \frac{1}{i}$ for all $1 \leq i \leq n$. \end{itemize} \begin{figure}[t]\label{sc1-tight} \centering %\scalebox{0.8}{\includegraphics {sc1-tight.pdf} \includegraphics[scale=0.7]{sc1-tight.pdf} \caption{A tight example for $SC1$.} \end{figure} The optimum solution is $S_0$ with a cost of $1 + \epsilon$ while $SC1$ returns the solution $\{S_1, \dots, S_n\}$ with a cost of $H_n = OPT \cdot \frac{H_n}{1+\epsilon}$. Since this holds for any small constant $\epsilon > 0$, the analysis is tight (even up to the constant). Interestingly, the above algorithm is essentially the best possible for set cover. \begin{theorem} [Lund and Yannakakis (92), Feige (96), Raz and Safra (97), Sudan (97)] ~ \begin{itemize} \item Unless $\P = \NP$, there is no $c \ln n$ approximation algorithm for set cover for some constant $0 < c < 1$. \item Unless $\NP \subseteq \DTIME(n^{O(\log\log n)})$, there is no $(1-\epsilon)\ln n$ approximation for set cover for all $\epsilon > 0$. \end{itemize} \end{theorem} \end{document}