%Created by Deeparnab Chakrabarty, 4th January, 2022
%Modified by Deeparnab Chakrabarty, 4th January, 2022

\documentclass[11pt]{article}
\def\lecnumber{1}
\def\lecdate{}
\def\lectopic{Introduction to Approximation Algorithms}



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




\begin{document}
	\def\moddate{4th Jan, 2022}
	\header

\def\mst{\mathsf{mst}}
\begin{itemize}
\item Welcome to a course on {\em approximation algorithms}. These are ``efficient'' algorithms which return a solution ``close'' to the desired solution, where close is deliberately left vague at this point. Why should one care? For many reasons. Most importantly, there are many problems for which finding the desired solution may be too hard. For instance, if we take an NP-hard problem\footnote{We assume the reader has familiarity with a basic undergraduate algorithms course, and also knows a bit of computational complexity. In particular, the reader understands  what an NP-hard problem is.} such as finding what is the longest path from $a$ to $b$ in a graph, then no one knows (and many don't expect) an efficient algorithm which runs in time at most some polynomial of the number of vertices and returns the correct solution on every graph. An approximate solution could be a path which may not be the longest but is at least half as long. 

Approximation also makes sense even when there are efficient algorithms known for a problem, but they are not efficient enough. For instance, a classic undergraduate algorithms problem is the {\em edit distance} problem : given two strings find the smallest number of inserts/deletes/swaps which takes the first string to the second. There is a dynamic programming algorithm whose running time is proportional to the product of the length of the two strings. But if the strings are, say, genome sequences, then each could have billions of characters, and it is infeasible to run such an algorithm.
Perhaps one can approximate this number much faster? Perhaps even without looking at whole of these strings.

%Finally, in many situations, the ``desired solution'' or the ``exact solution'' itself is unclear. For instance, if we have to cluster a bunch of points into parts. What is a desired solution? One could form a ``proxy'' and artificially define a desired solution. But in that case a ``close by'' solution could also be ``good enough''. I understand this is quite vague, but it is something to be aware of.

In this course, most of the effort will be spent on designing approximation algorithms for NP-hard problems. A formal definition follows in the next bullet point. 
The main objective, however,  is to explain an array of techniques that have been developed in the past four decades, and these techniques also find use in other notions of approximation.

\item {\bf \em A bit of formality.} Formally, an optimization problem $\Pi$ consists of instances $\cI$ and {\em feasible solutions}, $\cS$, to these instances. Each 
solution $S\in \cS$ is associated a cost $c(S)$.
To work with an example, the optimization problem {\em minimum spanning tree (MST)} has instances described by undirected graphs and costs 
on the edges. Solutions are the spanning trees of the graph, that is acyclic subgraphs containing all the vertices, and the cost of each solution is the sum of costs of the edges in the tree.
An optimization problem $\Pi$ is called a {\em minimization} problem if one wishes to find minimum cost solutions for every instance; it is called a {\em maximization} problem, if one wishes to find maximum cost (in which case cost is often called profit) solution.

An algorithm $\cA$ for an optimization problem $\Pi$, maps every instance $\cI$ to a feasible solution $S\in \cS$. So an MST algorithm takes an undirected graphs with edge costs and returns a spanning tree. Algorithm $\cA$ is called the {\bf optimal} algorithm for a minimization (respectively, maximization) problem  $\Pi$ if for each instance $\cI$, the algorithm returns the solution $S\in \cS$ of the {\em minimum} (respectively, {\em maximum}) cost. As mentioned above, for many optimization problems which are NP-hard, we do not expect to find optimal algorithms. This motivates the following definition.
 \begin{mdframed}[backgroundcolor=gray!05,topline=false,bottomline=false,leftline=false,rightline=false] 
\begin{definition}
	An algorithm $\cA$ for a minimization problem $\Pi$ is  an $\alpha$-factor approximation algorithm for $\Pi$, for some $\alpha \geq 1$, 
	if for every instance $\cI$, the solution $S_\cA$ returned by $\cA$ satisfies 
	\[
	c(S_\cA) \leq \alpha \cdot \min_{S\in \cS} c(S)
	\]
	An algorithm $\cA$ for a maximization problem $\Pi$ is  an $\alpha$-factor approximation algorithm for $\Pi$, for some $\alpha \leq 1$, 
	if for every instance $\cI$, the solution $S_\cA$ returned by $\cA$ satisfies 
	\[
	c(S_\cA) \geq  \alpha \cdot \max_{S\in \cS} c(S)
	\]
\end{definition}
\end{mdframed}
It should be clear that for any problem $\Pi$, we would like to design {\em polynomial time} algorithms with $\alpha$ as close to $1$ as possible. 
For NP-hard problems we don't expect to reach $\alpha = 1$. How close can we get? 

\item {\bf \em The Steiner Tree Problem.} Let us begin with a simple cousin of the minimum spanning tree algorithm which is already NP-hard.
As in the minimum spanning tree problem, the input is an undirected graph $G = (V,E)$ with costs on edges. Additionally, one is given a subset $R\subseteq V$ of {\em required vertices}.
The objective is to find the minimum cost subtree of $G$ which contains all the vertices of $R$. It may or may not contain all the vertices in $V\setminus R$, the so-called {\em Steiner vertices}.
Such trees are called Steiner trees.
For example, in~\Cref{fig:steiner-tree} the right-most tree is a spanning tree which is naturally a Steiner tree as well, while the middle tree is a Steiner tree since it doesn't contain the bottom-right Steiner vertex.

\begin{figure}[ht!]
	\includegraphics[trim = 0 200 100 50, clip, scale = 0.4]{figs/steiner-tree}
	\caption{A graph and two Steiner trees. The dark, filled circles are required vertices.}
	\label{fig:steiner-tree}
\end{figure}

It is perhaps surprising that although the minimum spanning tree has a simple exact algorithm, the Steiner tree problem is NP-hard. 
One therefore wishes to find approximation algorithms. An $\alpha$-approximation algorithm would take any graph $G$ and return a Steiner tree $T$ 
with the guarantee that $\cost(T) \leq \alpha \cdot \opt(G)$ where $\opt(G)$ is the cost of the minimum cost Steiner tree. Note that the algorithm would have no 
idea what $\opt(G)$ is, indeed even finding that value is NP-hard, and yet one should be able to argue that $\cost(T) \leq \alpha \cdot \opt(G)$.

\item {\bf \em A simple $2$-approximation algorithm.} Is there an algorithm that comes to mind? Here is one : since finding MST is easy, let's start by finding $T'$ which is an MST of $G$.
Starting with this tree $T'$, while there is a leaf which is a Steiner vertex, keep deleting it till we end up with a Steiner tree $T$ all of whose leaves are vertices in $R$. In the example of~\Cref{fig:steiner-tree}, the algorithm would return the tree to the right. And in that example, we see that $\cost(T) \leq \frac{10}{9}\cdot \opt(G)$, where the middle tree is the cheapest Steiner tree (figured by brute-force check). Does this mean the algorithm is a $\frac{10}{9}$-approximation? No! Because the approximation algorithm needs to return a tree within $\alpha\cdot \opt(G)$ for {\em every} graph $G$.
Indeed, the example shows that the factor can be no better than $\frac{10}{9}$, and in fact the factor is pretty bad.
\exer{\Coffeecup~
For any constant $\alpha$, describe a graph $G=(R\subseteq V,E)$ such that if $T$ is the tree returned by the above ``mst-and-prune'' algorithm, 
then $\cost(T) > \alpha \opt(G)$.
}

However, there is a simple $2$-approximation algorithm using minimum spanning trees, except that it is run on a different graph. 
Given $G = (V, E)$, $R\subseteq V$, and $c(e)$ on edges, define a {\em complete} graph $H = (R, F)$ with costs $w(u,v)$ for {\em all} pairs $u,v \in R\times R$, 
where 
\[
w(u,v) = \text{shortest cost path from $u$ to $v$ in $G$ with costs $c$}
\]
See~\Cref{fig:metric-completion}'s first arrow to get the metric completion for the graph in~\Cref{fig:steiner-tree}. Note that the metric completion can be obtained efficiently 
using, say, an all pairs shortest path algorithm.

\begin{figure}[ht!]
	\includegraphics[trim = 0 0 0 50, clip, scale = 0.4]{figs/metric-completion}
	\caption{Illustration of metric completion and the algorithm.}
	\label{fig:metric-completion}
\end{figure}

The algorithm is as follows : compute the MST in $H$ with weights $w$. Let this tree be $T' \subseteq H$. 
Start with an initial graph $T = (V,\emptyset)$. 
For every edge $e = (u,v) \in T'$ of weight $w(e)$, add the edges of the minimum cost path from $u$ to $v$ of cost $w(u,v)$ to $T$.
Note that we may be taking multiple copies of the same edge. After processing all edges in $T'$, we end up with a multi-graph $T$ 
such that (a) $T$ contains all the vertices in $R$, and (b) $\cost(T) = w(T') = \mst(H)$. Now delete edges arbitrarily from $T$ to make it a simple tree.
This  includes parallel copies and edges that form cycles, if any. In the example in~\Cref{fig:metric-completion}, the algorithm, in fac, recovers the optimum solution.
\exer{\Coffeecup~
	As the illustration shows, $T$ can contain parallel edges. Can it contain cycles of length $3$ or more? Why or why not?
}
 \begin{mdframed}[backgroundcolor=green!10,topline=false,bottomline=false,leftline=false,rightline=false] 
	\begin{center}
		\fbox{%
			\begin{varwidth}{\dimexpr\linewidth-2\fboxsep-2\fboxrule\relax}
				\begin{algorithmic}[1]
					\Procedure{MST-Steiner}{$G=(V,E)$, $R\subseteq V$, $c(e)$ on edges}:  
						\State Obtain $(H, w) \eq (G,c)$ via metric completion.
						\State $T'\eq \mst(H, w)$.
						\State For every edge $(u,v) \in T'$, add path to $T$.
						\State Prune $T$ till it becomes a tree.
						\State \Return $T$. 
					\EndProcedure
				\end{algorithmic}
			\end{varwidth}%
		}
	\end{center}
\end{mdframed}

\item {\bf \em Analysis.} The above algorithm in fact is ``not-too-bad'' on any graph.
\begin{thm}
	{\sc MST-Steiner} is a $2$-approximation algorithm. That is, for any $(G,c)$ with non-negative costs on edges, 
	the algorithm returns a Steiner tree $T$ with $\cost(T) \leq 2\opt(G)$.
\end{thm}
\begin{proof}
	We already know that $\cost(T) \leq \mst(H,w)$. To prove the theorem, it suffices to argue that $\mst(H,w) \leq 2\opt(G)$.
	To do this, consider the optimal Steiner tree $T^*$. The idea is to describe a tree $W$ in $H$ whose {\em weight} is at most $2\cost(T^*)$.
	
	Duplicate every edge in $T^*$ to get a multi-subgraph $T^{**}$ of $G$. Note that $\cost(T^{**})$, the cost of all the edges, is precisely $2\opt(G)$.
	Upon duplicating, we get that the degree of any vertex $v\in T^{**}$ is {\em even}.
	We are now going to use another graph theoretic fact. In any multi-graph, and in particular in $T^{**}$, where all vertices are even, there exists 
	a {\em walk} starting at any vertex $u$ and ending at the same vertex $u$ which traverses every edge {\em exactly} once. Such a walk is called the Eulerian walk or Eulerian tour.
	Let $\tau$ be this tour.
	
	Now we start $\tau$ at a required vertex $u$. Initialize $W\eq \emptyset$.
	Any time we visit another required vertex $v\in R$ in $\tau$, we add an edge $(u,v)$ to $W$ with cost $w(u,v)$. Note that 
this weight $w(u,v)$ is, by design, at most the {\em cost} of the edges in traversed in $\tau$. Upon continuing thus throughout $\tau$, 
we end with a subgraph $W$ of $H$ which is (a) spanning since all vertices of $R$ are visited by $\tau$ since $R\subseteq T^{**}$, 
and (b) the total weight of $W$ is at most $\cost(\tau) = \cost(T^{**}) = 2\opt(G)$.
Since the MST of $H$ wrt $w$ is only less than the weight of $W$, we get $\mst(H,w) \leq 2\opt(G)$. QED.
	\end{proof}

\exer{\Coffeecup~
For any constant $\eps > 0$, find a graph $G = (V,E)$ with costs $c$, such that {\sc MST-Steiner} returns 
a tree $T$ with $\cost(T) > (2- \eps)\opt(G)$. So, the approximation factor of the algorithm is no better than $2$.	
}

\end{itemize}

\subsection*{Notes} 
The Steiner tree problem has its roots in the following plane geometry problem : given three points $A,B,C$ on the place, which point $O$ minimizes
$|OA| + |OB| + |OC|$. This point is called the \href{https://en.wikipedia.org/wiki/Fermat_point}{Fermat-Torricelli point}. 
The $2$-approximation algorithm described above is one of the earliest approximation algorithms known, and can be found in the paper~\cite{Choukhmane78}
by Choukhmane. The first improvement of $\frac{11}{6}$ is in the paper~\cite{Zeli1993} by Zelikovsky. The current best approximation faction is 
$\ln 4 \approx 1.39$ which was obtained in the paper~\cite{ByrkaGRS2013} by Byrka, Grandoni, Rothvoss, and Sanita. 

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

\end{document}

