# Notes - ADS HT24, Approximation algorithms

### Flashcards

Suppose $\rho > 0$. What does it mean for algorithm $\mathcal A$ to be a $\rho$-approximation algorithm for a minimisation / maximisation problem $\mathcal P$?

For every instance $x$ of $\mathcal P$, the value $\mathcal A(x)$ of the solution produced by $\mathcal A$ and the optimal solution $\text{Opt}(x)$ satisfy:

- For minimisation problems: $\mathcal A(x) \le \rho \cdot \text{OPT}(x)$
- For maximisation problems: $\mathcal A(x) \ge \rho \cdot \text{OPT}(x)$

The $\mathbf{MinVertexCover}$ optimisation problem is:

- Input: Graph $G = (V, E)$
- Output: A vertex cover of minimum size

Give the pseudocode for an $2$-approximation algorithm for this problem.

- Input: Graph $G = (V, E)$
- Output: A vertex cover of minimum size

```
C = [] # the cover
while there is an edge e = (u, v) not covered by C:
add u to C
add v to C
return C
```

The $\mathbf{MinVertexCover}$ optimisation problem is:

- Input: Graph $G = (V, E)$
- Output: A vertex cover of minimum size

A greedy $2$-approximation algorithm for this problem is given by:

```
C = [] # the cover
while there is an edge e = (u, v) not covered by C:
add u to C
add v to C
return C
```

Quickly prove that this algorithm is indeed a valid $2$-approximation algorithm.

- Input: Graph $G = (V, E)$
- Output: A vertex cover of minimum size

```
C = [] # the cover
while there is an edge e = (u, v) not covered by C:
add u to C
add v to C
return C
```

Note that the algorithm implicitly computes a maximal matching (a matching is a collection of edges that have no common vertices, and a matching $M$ is maximal if there is no matching $M’$ such that $M \subseteq M’$):

```
C = [] # the cover
M = [] # the matching
while there is an edge e = (u, v) not covered by C:
add u to C
add v to C
add e to M
return C
```

Then $ \vert C \vert = 2 \vert M \vert $ ($M$ contains edges, and there are two vertices corresponding to each edge). This matching is maximal because of the structure of the while loop. We also must have that

\[\text{size of matching }M \le \text{size of any vertex cover }C\]since given any matching $M$, any vertex cover must cover all the edges in the matching, and each vertex in the vertex cover covers just one edge in the matching, but assumption that the edges in the matching are disjoint.

So in particular if $C^\star$ is the optimal such cover:

\[\text{size of matching }M \le \text{size of }C^\star\]Then, chaining these together:

\[|C| = 2M \le 2|C^\star|\]Suppose:

- $M$ is a matching (a collection of edges where no two edges share an endpoint)
- $C$ is a vertex cover

Quickly justify why

\[|M| \le |C|\]

The vertex cover must cover every edge in the matching, and since by assumption the edges in $M$ are disjoint from one another, one vertex in $C$ can only cover one edge.

What weak duality is there between matchings and vertex covers and in fact what (non-examinable) strong duality is there?

The strong duality is given by Kőnig’s theorem, which states that in bipartite graphs

\[\text{size of maximal matching } M = \text{size of vertex cover }C\]The $\mathbf{MinSetCover}$ optimisation problem is:

- Input: Set $U = \{u _ 1, \cdots, u _ n\}$, collection $\mathcal F = \{S _ 1, \cdots, S _ m\}$ of subsets of $U$.
- Output: The minimum number of sets from $\mathcal F$ whose union is $U$

Give the pseudocode for a greedy $(1 + \ln n) \vert C^\star \vert $-approximation algorithm for this problem.

- Input: Set $U = \{u _ 1, \cdots, u _ n\}$, collection $\mathcal F = \{S _ 1, \cdots, S _ m\}$ of subsets of $U$.
- Output: The minimum number of sets from $\mathcal F$ whose union is $U$

```
C = []
while there is an element of U not covered by C:
pick S \in \mathcal F that contains the max number of uncovered elements
C += S
output C
```

The $\mathbf{MinSetCover}$ optimisation problem is:

- Input: Set $U = \{u _ 1, \cdots, u _ n\}$, collection $\mathcal F = \{S _ 1, \cdots, S _ m\}$ of subsets of $U$.
- Output: The minimum number of sets from $\mathcal F$ whose union is $U$.

There is a greedy $\rho$-approximation algorithm for this problem, given by the psuedocode

```
C = []
while there is an element of U not covered by C:
pick S \in \mathcal F that contains the max number of uncovered elements
C += S
output C
```

Prove that $\rho < 1 + \ln n$.

- Input: Set $U = \{u _ 1, \cdots, u _ n\}$, collection $\mathcal F = \{S _ 1, \cdots, S _ m\}$ of subsets of $U$.
- Output: The minimum number of sets from $\mathcal F$ whose union is $U$.

```
C = []
while there is an element of U not covered by C:
pick S \in \mathcal F that contains the max number of uncovered elements
C += S
output C
```

Key idea: We can show the greedy strategy decreases the remaining uncovered elements by a multiplicative factor that depends on $k = \vert C^\star \vert $.

Some notation:

- Let $C^\star$ be an optimal solution to the problem
- $k = \vert C^\star \vert $

We want to show that $ \vert C \vert \le (1 + \ln n)k$.

Suppose at iteration $t$ of the while loop we have $n _ t$ elements that are yet to be covered. Then $C^\star$ gives a (potentially bad) covering of these elements of size $k$. Thus by the pigeonhole principle, there must exist some set in $C^\star$ that covers at least $n _ t / k$ of these elements (otherwise this cover wouldn’t be big enough, also note that we haven’t used this set yet since by assumption we are dealing with elements not in our cover).

This implies that

\[\begin{aligned} n_{t + 1} &\le n_t - \frac{n_t}{k} \\\\ &= \left(1 - \frac 1 k\right) n_t \end{aligned}\]Which implies in general

\[\begin{aligned} n_t &\le \left(1 - \frac 1 k \right)^t n \\\\ &\le e^{-t/k} \cdot n \end{aligned}\](since at the start of the algorithm there are $n$ elements yet to be covered, and are using the fact that for all $x \in R$, $1 + x \le e^x$ which can be proved by considering the Taylor expansion of $e^x$). We want $n _ t$ to be zero, or alternatively that $n _ t < 1$. This happens when $t > k \ln n$, since

\[\begin{aligned} n_t &< e^{-k \ln n / k} \cdot n \\\\ &= n^{-1} n \\\\ &= 1 \end{aligned}\]So after $k \ln n$ steps, $n _ t = 0$. Thus $ \vert C \vert < k \ln n$, or alternatively $ \vert C \vert \le 1 + k \ln n$. This implies that $ \vert C \vert \le (1 + \ln n)k$ as required.

The $\mathbf{MinTSP}$ problem is

- Input: Complete graph $G = (V, E)$, cost function $c : V \times V \to \mathbb R _ {\ge 0}$
- Output: A Hamiltonian cycle with minimum cost

Quickly prove that, unless $\mathbf P = \mathbf{NP}$, there is no $\alpha$-approximation algorithm for $\mathbf{MinTSP}$ for any $\alpha > 1$.

- Input: Complete graph $G = (V, E)$, cost function $c : V \times V \to \mathbb R _ {\ge 0}$
- Output: A Hamiltonian cycle with minimum cost

Let $\mathcal A$ be a polynomial time $\alpha$-approximation algorithm for the $\mathbf{MinTSP}$ problem. We aim to show that if such an algorithm exists, we can actually use it to decide whether an arbitrary graph has a Hamiltonian cycle, which is NP-complete.

Let $G = (V, E)$ be the graph for which we want to determine if it has a Hamiltonian cycle.

Define a cost function $c : V \times V \to \mathbb R _ {\ge 0}$ as follows:

\[c(u, v) = \begin{cases} \frac 1 n &\text{if } (u, v) \in E \\\\ 2\alpha &\text{otherwise (}G\text{ is not necc. complete)} \end{cases}\]This means $(V, c)$ defines an instance of $\mathbf{MinTSP}$. We want to show

\[G \text{ has Hamiltonian cycle} \iff (V, c) \text{ has approx. solution} \le \alpha\]Suppose $G$ has a Hamiltonian cycle. Then the TSP on $(V, c)$ has a solution with total cost $1$, which means $\mathcal A$ returns a solution with cost $\le \alpha$.

Suppose $G$ does not have a Hamiltonian cycle. Then any Hamiltonian cycle in $(V, c)$ uses an edge not in $G$, so $\mathcal A$ will return a solution with cost $\ge 2\alpha$.

Hence, by checking if the cost is $\le \alpha$, we can determine if an arbitrary graph has a Hamiltonian cycle.

The $\mathbf{MinTSP}$ problem is

- Input: Complete graph $G = (V, E)$, cost function $c : V \times V \to \mathbb R _ {\ge 0}$
- Output: A Hamiltonian cycle with minimum cost

This function is actually NP-hard to $\alpha$-approximate for any $\alpha > 1$. But, by adding the following restrictions:

- The cost function is symmetric
- The cost function satisfies the triangle inequality

We get the $\mathbf{MinMetricTSP}$ problem, which has enough additional structure to actually give a $2$-approximation algorithm. What is the rough idea behind the algorithm?

- Input: Complete graph $G = (V, E)$, cost function $c : V \times V \to \mathbb R _ {\ge 0}$
- Output: A Hamiltonian cycle with minimum cost

- The cost function is symmetric
- The cost function satisfies the triangle inequality

- Find an MST $T$
- Find a tour $\mathcal T$ (a walk that starts and ends at the same vertex, possibly repeating edges) by traversing edges of $T$ in DFS order
- Remove duplicated vertices in the tour (called “shortcutting”, this is where we use the triangle inequality and also the fact that the graph is complete)
- Output this list of vertices

The $\mathbf{MinTSP}$ problem is

- Input: Complete graph $G = (V, E)$, cost function $c : V \times V \to \mathbb R _ {\ge 0}$
- Output: A Hamiltonian cycle with minimum cost

This function is actually NP-hard to $\alpha$-approximate for any $\alpha > 1$. But, by adding the following restrictions:

- The cost function is symmetric
- The cost function satisfies the triangle inequality

We get the $\mathbf{MinMetricTSP}$ problem, which has enough additional structure to actually give a $2$-approximation algorithm:

- Find an MST $T$
- Find a tour $\mathcal T$ (a walk that starts and ends at the same vertex, possibly repeating edges) by traversing edges of $T$ in DFS order
- Remove duplicated vertices in the tour to obtain $\mathcal T’$ (called “shortcutting”, this is where we use the triangle inequality and also the fact that the graph is complete)
- Output this list of vertices

Quickly prove that this algorithm is a $2$-approximation algorithm.

- Input: Complete graph $G = (V, E)$, cost function $c : V \times V \to \mathbb R _ {\ge 0}$
- Output: A Hamiltonian cycle with minimum cost

- The cost function is symmetric
- The cost function satisfies the triangle inequality

Let $c(\cdot)$ denote the cost of some graph by summing along the costs along the edges. We want to show $c(\mathcal T’) \le 2\text{OPT}$.

- Note that $c(\mathcal T’) \le c(\mathcal T)$ because of the triangle inequality. If $\mathcal T$ visits vertices $v _ 1, \cdots, v _ {i-1}, v _ i, v _ {i+1}, v _ n$ where $v _ i$ is repeated, then $c(\mathcal T) - c(\mathcal T \setminus \{v _ i\}) = c(v _ {i-1}, v _ i) + c(v _ i, v _ {i+1}) - c(v _ {i-1}, c _ {i+1}) \ge 0$.
- Also $c(\mathcal T) = 2c(T)$, since we double the number of edges in the MST.
- Finally $c(T) \le \text{OPT}$, since an optimal TSP induces a spanning tree, but we could just remove edges until we get a spanning tree, which must be at least as large as $c(T)$.

Hence overall:

\[c(\mathcal T') \le c(\mathcal T) \le 2c(T) \le 2\text{OPT}\]What is a tour of a graph?

A walk that starts and ends at the same vertex, and visits every vertex at least once.

What is a walk on a graph?

A sequence of vertices edges in a graph.

The $\mathbf{MinTSP}$ problem is

- Input: Complete graph $G = (V, E)$, cost function $c : V \times V \to \mathbb R _ {\ge 0}$
- Output: A Hamiltonian cycle with minimum cost

In proving that this is actually NP-hard to $\alpha$-approximate for any $\alpha > 1$, we show that we can solve any instance of deciding $\textbf{HamiltonianCycle}$ with this approximation by taking a graph $G = (V, E)$ and constructing a cost function $c : V \times V \to \mathbb R _ {\ge 0}$. How is this cost function defined, and why does it work?

- Input: Complete graph $G = (V, E)$, cost function $c : V \times V \to \mathbb R _ {\ge 0}$
- Output: A Hamiltonian cycle with minimum cost

Then if the graph contains a Hamiltonian cycle, the minimum travelling salesperson tour has weight $1$. If it doesn’t, then the minimum tour has cost at least $\alpha$, which means we could distinguish these cases with our approximation algorithm.

Suppose we have a minimisation problem that we’re aiming to show is NP-hard to polynomially approximate within a factor $1 + \frac{1}{n+1}$ where $n$ is the size of an instance. The standard technique for showing no approximation algorithms exist is to show that they could be used to decide an NP-hard decision problem in polynomial time.

To do this, fix some instance $I$ of the decision problem. What “inequalities” do we want that would let us distinguish between positive instances of the decision problem and negative instances of the decision problem?

- $I$ is a positive instance: we can come up with an instance of the minimisation problem with cost $\le n+1$.
- $I$ is a negative instance: The minimisation problem has cost $> n + 1$

This is because $(n+1) \cdot (1 + \frac {1}{n+1}) = n + 1 + 1 = n + 2$, so the approximation algorithm would have to tell if it was a positive instance.